On existentially first-order definable languages and their relation to NP
Borchert, Bernd ; Kuske, Dietrich ; Stephan, Frank
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999), p. 259-269 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@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},
     volume = {33},
     year = {1999},
     pages = {259-269},
     mrnumber = {1728426},
     zbl = {0949.03035},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 259-269. http://gdmltest.u-ga.fr/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