Tailoring recursion for complexity
From MaRDI portal
Publication:4858828
DOI10.2307/2275767zbMath0837.03034MaRDI QIDQ4858828
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
03D15: Complexity of computation (including implicit computational complexity)
03C13: Model theory of finite structures
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Algebraic and logical characterizations of deterministic linear time classes, Implicit complexity over an arbitrary structure: Quantifier alternations, Intensional Properties of Polygraphs, Computational Complexity Via Finite Types
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