We show that in the context of orthogonal term rewriting systems, derivational complexity is an invariant cost model, both in innermost and in outermost reduction. This has some interesting consequences for (asymptotic) complexity analysis, since many existing methodologies only guarantee bounded derivational complexity.
U. Dal Lago, S. Martini (2010). Derivational Complexity is an Invariant Cost Model. BERLIN HEIDELBERG : Springer [10.1007/978-3-642-15331-0_7].
Derivational Complexity is an Invariant Cost Model
DAL LAGO, UGO;MARTINI, SIMONE
2010
Abstract
We show that in the context of orthogonal term rewriting systems, derivational complexity is an invariant cost model, both in innermost and in outermost reduction. This has some interesting consequences for (asymptotic) complexity analysis, since many existing methodologies only guarantee bounded derivational complexity.File in questo prodotto:
Eventuali allegati, non sono esposti
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
