Capturing complexity classes by fragments of second-order logic
From MaRDI portal
Publication:1193408
DOI10.1016/0304-3975(92)90149-AzbMath0780.68040MaRDI QIDQ1193408
Publication date: 27 September 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
expressive powercomplexity classeslogspaceexistential fragmentsfragments of second-order logicsecond-order Horn logicsecond-order Krom logic
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
2000 Annual Meeting of the Association for Symbolic Logic, Arithmetical definability and computational complexity, A logical approach to locality in pictures languages, Existential Fixed-Point Logic as a Fragment of Second-Order Logic, Tailoring recursion for complexity, The Expressive Power of Higher-Order Datalog, Inductive definitions in logic versus programs of real-time cellular automata, On the complexity of single-rule datalog queries., Capturing the polynomial hierarchy by second-order revised Krom logic, Quantified Constraint Satisfaction and the Polynomially Generated Powers Property, A second-order system for polytime reasoning based on Grädel's theorem., Unnamed Item, Tailoring recursion for complexity, Expressive power and abstraction in Essence, Complexity and expressive power of second‐order extended Horn logic, Quantified constraint satisfaction and the polynomially generated powers property, Expressivity and Complexity of Dependence Logic, Rewriting Conjunctive Queries over Description Logic Knowledge Bases, Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The expressive power of stratified logic programs
- Henkin quantifiers and complete problems
- Fixed-point extensions of first-order logic
- The method of forced enumeration for nondeterministic automata
- Descriptive characterizations of computational complexity
- Number of quantifiers is better than number of tape cells
- Symmetric space-bounded computation
- Upper and lower bounds for first order expressibility
- Complete problems for deterministic polynomial time
- The polynomial-time hierarchy
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Structure and complexity of relational queries
- Horn clause queries and generalizations
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Relational queries computable in polynomial time
- Languages that Capture Complexity Classes
- Unification as a complexity measure for logic programming
- Nondeterministic Space is Closed under Complementation
- New problems complete for nondeterministic log space
- Expressibility and Parallel Complexity
- The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
