Tailoring recursion for complexity

DOI10.2307/2275767zbMATH Open0837.03034OpenAlexW2089982125MaRDI QIDQ4858828FDOQ4858828

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

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

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)

Cites Work

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

Cited In (13)

• Bases for \(\mathrm{AC}^{0}\) and other complexity classes
• New substitution bases for complexity classes
• Title not available (Why is that?)
• Computational Complexity Via Finite Types
• Algebraic and logical characterizations of deterministic linear time classes
• Title not available (Why is that?)
• 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
• Automatically Introducing Tail Recursion in CakeML
• A difference in complexity between recursion and tail recursion

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)