Capturing complexity classes by fragments of second-order logic

DOI10.1016/0304-3975(92)90149-AzbMath0780.68040MaRDI QIDQ1193408

Erich Grädel

Publication date: 27 September 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

expressive powercomplexity classeslogspaceexistential fragmentsfragments of second-order logicsecond-order Horn logicsecond-order Krom logic

Mathematics Subject Classification ID

Related Items (19)

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

This page was built for publication: Capturing complexity classes by fragments of second-order logic