Tailoring recursion for complexity

DOI10.2307/2275767zbMath0837.03034OpenAlexW2089982125MaRDI QIDQ4858828

Erich Grädel, Yuri Gurevich

Publication date: 19 December 1995

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2275767

zbMATH Keywords

polynomial timefinite model theorycomplexity classesdescriptive complexity theory

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Algebraic and logical characterizations of deterministic linear time classes ⋮ Computational Complexity Via Finite Types ⋮ Implicit complexity over an arbitrary structure: Quantifier alternations ⋮ Intensional Properties of Polygraphs

Cites Work

• Fixed-point extensions of first-order logic
• The method of forced enumeration for nondeterministic automata
• The complexity of optimization problems
• Upper and lower bounds for first order expressibility
• Datalog extensions for database queries and updates
• Capturing complexity classes by fragments of second-order logic
• An algebra and a logic for \(NC^ 1\)
• Weak Second‐Order Arithmetic and Finite Automata
• A logic for constant-depth circuits
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• Nondeterministic Space is Closed under Complementation

This page was built for publication: Tailoring recursion for complexity