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

DOI10.1051/ITA:1999116MaRDI QIDQ4718893zbMATH OpenOpenAlexFDO

Authors 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/, https://eudml.org/doc/222021

zbMATH Keywords

automataexistential definabilityfirst-order logicpolynomial-time hierarchyregular language

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)

Review text

The authors consider an extended first-order logic, denoted by FOX, which is first-order logic augmented with the additional functions min, max (both 0-ary) and \(+1\) and \(-1\) (both 1-ary). FOX is strictly more powerful than first-order logic on the level of existential definability. A language \(L\) is existentially definable in FOX if there is an existentially quantified sentence of FOX in prenex normal form defining \(L\). The main result of the paper is Theorem 3.4.: Let \(L\) be a regular language. Assuming that \(\text{PH}\) (the polynomial hierarchy) does not collapse, the following holds: (1) \(L-\text{P}=\text{P}\) iff \(L\) is quantifier-free definable in FOX but not trivial; (2) \(L-\text{P}=\text{NP}\) iff \(L\) is existentially but not quantifier-free definable in FOX; (3) \(L-\text{P}=\text{co-NP}\) iff \(L\) is universally but not quantifier-free definable in FOX. The proof of these sentences uses the characterization of the automata of the existentially first-order definable languages. In the final part of the paper some open problems are presented.

Recommendations

• On existentially first-order definable languages and their relation to NP
• Definability of Languages by Generalized First-Order Formulas over (N,+)
• Definability of Languages by Generalized First-Order Formulas over $(\mathbb{N},+)$
• First-order definable languages
• First-order logic definability of free languages
• Non-definability of Languages by Generalized First-order Formulas over (N,+)
• The Exact Complexity of the First-Order Logic Definability Problem
• First-order definability on finite structures

Cites work

• A uniform approach to define complexity classes
• Classifying regular events in symbolic logic
• Counting classes: Thresholds, parity, mods, and fewness
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• Lindström quantifiers and leaf language definability
• On the acceptance power of regular languages
• On unique satisfiability and the threshold behavior of randomized reductions
• Polynomial closure and unambiguous product
• PP is as Hard as the Polynomial-Time Hierarchy
• The Boolean Hierarchy I: Structural Properties

Cited in

(11)

• Machines that can output empty words
• Perfect correspondences between dot-depth and polynomial-time hierarchies
• A reducibility for the dot-depth hierarchy
• Non-definability of Languages by Generalized First-order Formulas over (N,+)
• Hierarchies and reducibilities on regular languages related to modulo counting
• On existentially first-order definable languages and their relation to NP
• Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
• THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS
• Languages polylog-time reducible to dot-depth 1/2
• Autoreducibility, mitoticity, and immunity
• Fine hierarchies and m-reducibilities in theoretical computer science

This page was built for publication: On Existentially First-Order Definable Languages and Their Relation to NP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4718893)