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},
zbl = {0949.03035},
mrnumber = {1728426},
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
DA  - 1999///
SP  - 259
EP  - 269
VL  - 33
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1999__33_3_259_0/
UR  - https://zbmath.org/?q=an%3A0949.03035
UR  - https://www.ams.org/mathscinet-getitem?mr=1728426
LA  - en
ID  - ITA_1999__33_3_259_0
ER  - 
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 1181036 | Zbl 0760.68028

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

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

[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 972671 | Zbl 0676.68011

[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 1339547 | Zbl 0837.68026

[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 1310801

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

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

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

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

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