A Path Order for Rewrite Systems that Compute Exponential Time Functions

DOI10.4230/LIPIcs.RTA.2011.123zbMath1236.68118arXiv1010.1128OpenAlexW2101896977MaRDI QIDQ5389077

Martin Avanzini, Naohi Eguchi, Georg Moser

Publication date: 24 April 2012

Full work available at URL: https://arxiv.org/abs/1010.1128

zbMATH Keywords

implicit computational complexityruntime complexityexponential time functions

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (5)

From Jinja bytecode to term rewriting: a complexity reflecting transformation ⋮ Read/write factorizable programs ⋮ Unnamed Item ⋮ A new order-theoretic characterisation of the polytime computable functions ⋮ Type-based analysis of logarithmic amortised complexity

This page was built for publication: A Path Order for Rewrite Systems that Compute Exponential Time Functions