A new order-theoretic characterisation of the polytime computable functions
From MaRDI portal
Publication:2346988
DOI10.1016/j.tcs.2015.03.003zbMath1327.68142OpenAlexW2162002559WikidataQ43205764 ScholiaQ43205764MaRDI QIDQ2346988
Naohi Eguchi, Georg Moser, Martin Avanzini
Publication date: 26 May 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.03.003
Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
A combination framework for complexity ⋮ From Jinja bytecode to term rewriting: a complexity reflecting transformation ⋮ Read/write factorizable programs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Quasi-interpretations. A way to control resources
- Matrix interpretations for proving termination of term rewriting
- The realm of primitive recursion
- A new recursion-theoretic characterization of the polytime functions
- Analysing the implicit complexity of programs.
- Algorithms with polynomial interpretation termination proof
- Polynomial Path Orders
- A new function algebra of EXPTIME functions by safe nested recursion
- A Combination Framework for Complexity
- Tyrolean Complexity Tool: Features and Usage.
- Joint Spectral Radius Theory for Automated Complexity Analysis of Rewrite Systems
- Proving Quadratic Derivational Complexities Using Context Dependent Interpretations
- Automated Complexity Analysis Based on the Dependency Pair Method
- Complexity Analysis by Graph Rewriting
- On tiered small jump operators
- On Constructor Rewrite Systems and the Lambda-Calculus
- Multi-dimensional Rankings, Program Termination, and Complexity Bounds of Flowchart Programs
- Automated Complexity Analysis Based on Context-Sensitive Rewriting
- Amortised Resource Analysis and Typed Polynomial Interpretations
- SPEED
- A Path Order for Rewrite Systems that Compute Exponential Time Functions
- Closing the Gap Between Runtime Complexity and Polytime Computability.
- Modular Complexity Analysis via Relative Complexity
- Complexity Analysis by Rewriting
- Computability of Recursive Functions
- Guest editorial
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
This page was built for publication: A new order-theoretic characterisation of the polytime computable functions