Tailoring recursion for complexity
From MaRDI portal
Publication:4858828
DOI10.2307/2275767zbMATH Open0837.03034OpenAlexW2089982125MaRDI QIDQ4858828FDOQ4858828
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
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 (7)
- Computational Complexity Via Finite Types
- Algebraic and logical characterizations of deterministic linear time classes
- Implicit complexity over an arbitrary structure: Quantifier alternations
- A new approach to recursion removal
- Tiering as a Recursion Technique
- Intensional properties of polygraphs
- Automatically Introducing Tail Recursion in CakeML
Recommendations
- Tailoring recursion for complexity 👍 👎
- New Computational Paradigms 👍 👎
- Title not available (Why is that?) 👍 👎
- The Tangled Allure of Recursion 👍 👎
- The intrinsic difficulty of recursive functions 👍 👎
- Title not available (Why is that?) 👍 👎
- 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 👍 👎
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)
