# On Existentially First-Order Definable Languages and Their Relation to NP

Bernd Borchert; Dietrich Kuske; Frank Stephan

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 33, Issue: 3, page 259-269
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topBorchert, Bernd, Kuske, Dietrich, and Stephan, Frank. "On Existentially First-Order Definable Languages and Their Relation to NP." RAIRO - Theoretical Informatics and Applications 33.3 (2010): 259-269. <http://eudml.org/doc/222021>.

@article{Borchert2010,

abstract = {
Under the assumption that the Polynomial-Time Hierarchy does not collapse
we show for a regular language L:
the unbalanced polynomial-time leaf language class determined by L
equals iff L is existentially but not
quantifierfree definable in FO[<, min, max, +1, −1].
Furthermore, no such
class lies properly between NP and co-1-NP or NP⊕co-NP.
The proofs rely on a result of Pin and Weil
characterizing
the automata of existentially first-order definable languages.
},

author = {Borchert, Bernd, Kuske, Dietrich, Stephan, Frank},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Leaf languages; NP; first-order definable languages.; polynomial-time hierarchy; first-order logic; existential definability; regular language; automata},

language = {eng},

month = {3},

number = {3},

pages = {259-269},

publisher = {EDP Sciences},

title = {On Existentially First-Order Definable Languages and Their Relation to NP},

url = {http://eudml.org/doc/222021},

volume = {33},

year = {2010},

}

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

DA - 2010/3//

PB - EDP Sciences

VL - 33

IS - 3

SP - 259

EP - 269

AB -
Under the assumption that the Polynomial-Time Hierarchy does not collapse
we show for a regular language L:
the unbalanced polynomial-time leaf language class determined by L
equals iff L is existentially but not
quantifierfree definable in FO[<, min, max, +1, −1].
Furthermore, no such
class lies properly between NP and co-1-NP or NP⊕co-NP.
The proofs rely on a result of Pin and Weil
characterizing
the automata of existentially first-order definable languages.

LA - eng

KW - Leaf languages; NP; first-order definable languages.; polynomial-time hierarchy; first-order logic; existential definability; regular language; automata

UR - http://eudml.org/doc/222021

ER -

## References

top- R. Beigel and J. Gill, Counting classes: Thresholds, parity, mods, and fewness. Theoret. Comput. Sci.103 (1992) 3-23.
- B. Borchert, On the acceptance power of regular languages. Theoret. Comput. Sci.148 (1995) 207-225.
- D.P. Bovet, P. Crescenzi and R. Silvestri, A uniform approach to define complexity classes. Theoret. Comput. Sci.104 (1992) 263-283.
- H.-J. Burtschick and H. Vollmer, Lindström Quantifiers and Leaf Language Definability. Internat. J. Found. Comput. Sci.9 (1998) 277-294.
- 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.
- 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.
- 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.
- R. McNaughton and S. Papert, Counter-Free Automata, MIT Press, Cambridge, MA (1971).
- J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Comput. Systems30 (1997) 383-422.
- H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity, Birkhäuser, Boston (1994).
- W. Thomas, Classifying regular events in symbolic logic. J. Comput. System Sci.25 (1982) 360-376.
- S. Toda, PP is as hard as the Polynomial-Time Hierarchy. SIAM J. Comput.20 (1991) 865-877.

## Citations in EuDML Documents

top- Victor L. Selivanov, Relating automata-theoretic hierarchies to complexity-theoretic hierarchies
- Victor L. Selivanov, Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
- Victor L. Selivanov, Hierarchies and reducibilities on regular languages related to modulo counting
- Victor L. Selivanov, Hierarchies and reducibilities on regular languages related to modulo counting

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.