Closing the Gap Between Runtime Complexity and Polytime Computability.

DOI10.4230/LIPIcs.RTA.2010.33zbMath1236.68119OpenAlexW1543209434MaRDI QIDQ5389134

Martin Avanzini, Georg Moser

Publication date: 25 April 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_daf8.html

zbMATH Keywords

graph rewritingterm rewritingcomplexity analysispolytime computability

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

A combination framework for complexity, On the enumeration of closures and environments with an application to random generation, On sharing, memoization, and polynomial time, Size-based termination of higher-order rewriting, Linear pattern matching of compressed terms and polynomial rewriting, Unnamed Item, A Dependency Pair Framework for Innermost Complexity Analysis of Term Rewrite Systems, (In)efficiency and reasonable cost models, A new order-theoretic characterisation of the polytime computable functions, Analyzing innermost runtime complexity of term rewriting by dependency pairs