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
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
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 (9)
- 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
- Intensional properties of polygraphs
- 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)
