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

DOI10.1051/ita:1999116zbMath0949.03035OpenAlexW1964316889MaRDI QIDQ4718893

Bernd Borchert, Dietrich Kuske, Frank Stephan

Publication date: 6 December 2000

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_1999__33_3_259_0/

zbMATH Keywords

automatafirst-order logicregular languagepolynomial-time hierarchyexistential definability

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies ⋮ Languages polylog-time reducible to dot-depth 1/2 ⋮ Autoreducibility, mitoticity, and immunity ⋮ Perfect correspondences between dot-depth and polynomial-time hierarchies ⋮ Hierarchies and reducibilities on regular languages related to modulo counting ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ Machines that can output empty words ⋮ THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS ⋮ A reducibility for the dot-depth hierarchy

Cites Work

• Unnamed Item
• On the acceptance power of regular languages
• Classifying regular events in symbolic logic
• A uniform approach to define complexity classes
• Polynomial closure and unambiguous product
• On unique satisfiability and the threshold behavior of randomized reductions
• PP is as Hard as the Polynomial-Time Hierarchy
• The Boolean Hierarchy I: Structural Properties
• LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY
• Counting classes: Thresholds, parity, mods, and fewness