Time-Complexity Semantics for Feasible Affine Recursions

DOI10.1007/978-3-540-73001-9_22MaRDI QIDQ5425322zbMATH OpenOpenAlexFDO

Authors Norman Danner, James S. Royer

Publication date 13 November 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73001-9_22

Mathematics Subject Classification ID

Logic in computer science (03B70) Applications of computability and recursion theory (03D80) Functional programming and lambda calculus (68N18) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Time-space tradeoffs in algebraic complexity theory
• Polynomial time computation in the context of recursive analysis
• On genuinely time bounded computations
• scientific article; zbMATH DE number 3596249
• Almost-everywhere complexity hierarchies for nondeterministic time
• Linear time and branching time semantics for recursion with merge
• Non-uniform polytime computation in the infinitary affine lambda-calculus
• A new recursion-theoretic characterization of the polytime functions
• scientific article; zbMATH DE number 17551

Cited in

(3)

• All Linear-Time Congruences for Familiar Operators Part 2: Infinite LTSs
• Adventures in time and space
• Adventures in time and space

This page was built for publication: Time-Complexity Semantics for Feasible Affine Recursions

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