Tailoring recursion for complexity

DOI10.2307/2275767MaRDI QIDQ4858828zbMATH OpenOpenAlexFDO

Authors 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

complexity classesfinite model theorypolynomial timedescriptive complexity theory

Mathematics Subject Classification ID

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

Recommendations

• Tailoring recursion for complexity
• New Computational Paradigms
• scientific article; zbMATH DE number 4037837
• The tangled allure of recursion
• The intrinsic difficulty of recursive functions
• scientific article; zbMATH DE number 782018
• Recursion Schemes for Dynamic Programming
• Abstract recursion and intrinsic complexity
• Optimizing structural recursion in functional programs
• On a complexity-based way of constructivizing the recursive functions

Cites work

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

Cited in

(13)

• Bases for \(\mathrm{AC}^{0}\) and other complexity classes
• New substitution bases for complexity classes
• scientific article; zbMATH DE number 3995649 (Why is no real title available?)
• Computational Complexity Via Finite Types
• Algebraic and logical characterizations of deterministic linear time classes
• scientific article; zbMATH DE number 2163035 (Why is no real title available?)
• Implicit complexity over an arbitrary structure: Quantifier alternations
• A new approach to recursion removal
• Tiering as a Recursion Technique
• A recursion-theoretic approach to NP
• Intensional properties of polygraphs
• A difference in complexity between recursion and tail recursion
• Automatically Introducing Tail Recursion in CakeML

This page was built for publication: Tailoring recursion for complexity

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