@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] Counting classes: Thresholds, parity, mods, and fewness. Theoret. Comput. Sci. 103 (1992) 3-23. | MR | Zbl
and ,[2] On the acceptance power of regular languages. Theoret. Comput. Sci. 148 (1995) 207-225. | MR | Zbl
,[3] A uniform approach to define complexity classes. Theoret. Comput. Sci. 104 (1992) 263-283. | MR | Zbl
, and ,[4] Lindström Quantifiers and Leaf Language Definability. Internat. J. Found. Comput. Sci. 9 (1998) 277-294.
and ,[5] The Boolean Hierarchy I: Structural properties. SIAM J. Comput. 17 (1988) 1232-1252. | MR | Zbl
, , , , , and ,[6] On unique satisfiability and the threshold behaviour of randomized reductions. J. Comput. System Sci. 50 (1995) 359-373. | MR | Zbl
, and ,[7] On the power of polynomial-time bit-computations, In: Proc. 8th Structure in Complexity Theory Conference, IEEE Computer Society Press (1993) 200-207. | MR
, , , and ,[8] Counter-Free Automata, MIT Press, Cambridge, MA (1971). | MR | Zbl
and ,[9] Polynomial closure and unambiguous product. Theory Comput. Systems 30 (1997) 383-422. | MR | Zbl
and ,[10] Finite Automata, Formal Logic, and Circuit Complexity, Birkhäuser, Boston (1994). | MR | Zbl
,[11] Classifying regular events in symbolic logic. J. Comput. System Sci. 25 (1982) 360-376. | MR | Zbl
,[12] PP is as hard as the Polynomial-Time Hierarchy. SIAM J. Comput. 20 (1991) 865-877. | MR | Zbl
,