A new order-theoretic characterisation of the polytime computable functions

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

zbMATH Keywords

term rewritingcomplexity analysisautomationimplicit computational complexity

Mathematics Subject Classification ID

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

• SPEED

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