Tailoring recursion for complexity

DOI10.1007/3-540-58201-0_62MaRDI QIDQ4632420zbMATH OpenOpenAlexFDO

Authors Erich Grädel, Yuri Gurevich

Publication date 29 April 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-58201-0_62

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• Tailoring recursion for complexity
• An algebra and a logic for \(NC^ 1\)
• scientific article; zbMATH DE number 2163035
• Functions and functional on finite systems
• Function algebraic characterizations of the polytime 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
• Functions and functional on finite systems
• scientific article; zbMATH DE number 4170889 (Why is no real title available?)
• scientific article; zbMATH DE number 4008383 (Why is no real title available?)
• scientific article; zbMATH DE number 4106276 (Why is no real title available?)
• scientific article; zbMATH DE number 3711948 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 515737 (Why is no real title available?)

Cited in

(6)

• A new approach to recursion removal
• Recursion versus tail recursion over \(\overline{\mathbb{F}}_p\)
• Tiering as a Recursion Technique
• Functions and functional on finite systems
• Tailoring recursion for complexity
• 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 Q4632420)