On existentially first-order definable languages and their relation to NP
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) no. 3, pp. 259-269. 
@article{ITA_1999__33_3_259_0,
     author = {Borchert, Bernd and Kuske, Dietrich and Stephan, Frank},
     title = {On existentially first-order definable languages and their relation to {NP}},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {259--269},
     publisher = {EDP-Sciences},
     volume = {33},
     number = {3},
     year = {1999},
     mrnumber = {1728426},
     zbl = {0949.03035},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1999__33_3_259_0/}
}
TY  - JOUR
AU  - Borchert, Bernd
AU  - Kuske, Dietrich
AU  - Stephan, Frank
TI  - On existentially first-order definable languages and their relation to NP
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1999
SP  - 259
EP  - 269
VL  - 33
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1999__33_3_259_0/
LA  - en
ID  - ITA_1999__33_3_259_0
ER  - 
%0 Journal Article
%A Borchert, Bernd
%A Kuske, Dietrich
%A Stephan, Frank
%T On existentially first-order definable languages and their relation to NP
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1999
%P 259-269
%V 33
%N 3
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1999__33_3_259_0/
%G en
%F ITA_1999__33_3_259_0
Borchert, Bernd; Kuske, Dietrich; Stephan, Frank. On existentially first-order definable languages and their relation to NP. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) no. 3, pp. 259-269. http://www.numdam.org/item/ITA_1999__33_3_259_0/

[1] R. Beigel and J. Gill, Counting classes: Thresholds, parity, mods, and fewness. Theoret. Comput. Sci. 103 (1992) 3-23. | MR | Zbl

[2] B. Borchert, On the acceptance power of regular languages. Theoret. Comput. Sci. 148 (1995) 207-225. | MR | Zbl

[3] D. P. Bovet, P. Crescenzi and R. Silvestri, A uniform approach to define complexity classes. Theoret. Comput. Sci. 104 (1992) 263-283. | MR | Zbl

[4] H.-J. Burtschick and H. Vollmer, Lindström Quantifiers and Leaf Language Definability. Internat. J. Found. Comput. Sci. 9 (1998) 277-294.

[5] J.-Y. Cai, T. Gundermann, J. Hartmanis, L. A. Hemachandra, V. Sewelson, K. Wagner and G. Wechsung, The Boolean Hierarchy I: Structural properties. SIAM J. Comput. 17 (1988) 1232-1252. | MR | Zbl

[6] R. Chang, J. Kadin and P. Rohatgi, On unique satisfiability and the threshold behaviour of randomized reductions. J. Comput. System Sci. 50 (1995) 359-373. | MR | Zbl

[7] U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer and K. Wagner, On the power of polynomial-time bit-computations, In: Proc. 8th Structure in Complexity Theory Conference, IEEE Computer Society Press (1993) 200-207. | MR

[8] R. Mcnaughton and S. Papert, Counter-Free Automata, MIT Press, Cambridge, MA (1971). | MR | Zbl

[9] J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Comput. Systems 30 (1997) 383-422. | MR | Zbl

[10] H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity, Birkhäuser, Boston (1994). | MR | Zbl

[11] W. Thomas, Classifying regular events in symbolic logic. J. Comput. System Sci. 25 (1982) 360-376. | MR | Zbl

[12] S. Toda, PP is as hard as the Polynomial-Time Hierarchy. SIAM J. Comput. 20 (1991) 865-877. | MR | Zbl