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.
The authors are partially supported by PRIN project “CONCERTO” and FIRB grant RBIN04M8S8, “Intern. Inst. for Applicable Math.”
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Asperti, A., Coppola, P., Martini, S.: Optimalduplication is not elementary recursive. Inf. Comput. 193(1), 21–56 (2004)
Asperti, A., Mairson, H.G.: Parallel beta reduction is not elementary recursive. Inf. Comput. 170(1), 49–80 (2001)
Avanzini, M., Moser, G.: Complexity analysis by rewriting. In: Garrigue, J., Hermenegildo, M.V. (eds.) FLOPS 2008. LNCS, vol. 4989, pp. 130–146. Springer, Heidelberg (2008)
Barendregt, H., Eekelen, M., Glauert, J., Kennaway, J., Plasmeijer, M., Sleep, M.: Term graph rewriting. In: de Bakker, J., Nijman, A., Treleaven, P. (eds.) Parallel Languages on PARLE: Parallel Architectures and Languages Europe, vol. II, pp. 141–158. Springer, Heidelberg (1986)
Barendsen, E.: Term graph rewriting. In: Bezem, T.M., Klop, J.W., de Vrijer, R. (eds.) Term Rewriting Systems, ch. 13, pp. 712–743. Cambridge Univ. Press, Cambridge (2003)
Bonfante, G., Marion, J.-Y., Moyen, J.-Y.: On lexicographic termination ordering with space bound certifications. In: Bjørner, D., Broy, M., Zamulin, A.V. (eds.) PSI 2001. LNCS, vol. 2244, pp. 482–493. Springer, Heidelberg (2001)
Dal Lago, U., Martini, S.: On constructor rewriting systems and the lambda calculus. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5556, pp. 163–174. Springer, Heidelberg (2009)
Gurevich, Y.: On Kolmogorov machines and related issues. Bulletin of the European Association for Theoretical Computer Science 35, 71–82 (1988)
Hirokawa, N., Moser, G.: Automated complexity analysis based on the dependency pair method. In: Armando, A., Baumgartner, P., Dowek, G. (eds.) IJCAR 2008. LNCS (LNAI), vol. 5195, pp. 364–379. Springer, Heidelberg (2008)
Jones, N.D.: Computability and Complexity from a Programming Perspective. MIT Press, Cambridge (1997)
Knuth, D.: The Art of Computer Programming, vol. 1, pp. 462–463. Prentice Hall, Englewood Cliffs (1973)
Kolmogorov, A.N., Uspensky, V.: On the definition of algorithm. In: Uspekhi Mat. Naut., vol. 13(4), pp. 3–28 (1958)
Marion, J.-Y.: Analysing the implicit complexity of programs. Inform. and Comp. 183(1), 2–18 (2003)
Plump, D.: Graph-reducible term rewriting systems. Graph-Grammars and Their Application to Computer Science, pp. 622–636 (1990)
Schönage, A.: Storage modification machines. SIAM J. Comput. 9, 490–508 (1980)
van Emde Boas, P.: Machine models and simulation. In: Handbook of Theoretical Computer Science. Algorithms and Complexity (A), vol. A, pp. 1–66. MIT Press, Cambridge (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dal Lago, U., Martini, S. (2010). Derivational Complexity Is an Invariant Cost Model. In: van Eekelen, M., Shkaravska, O. (eds) Foundational and Practical Aspects of Resource Analysis. FOPARA 2009. Lecture Notes in Computer Science, vol 6324. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15331-0_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-15331-0_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15330-3
Online ISBN: 978-3-642-15331-0
eBook Packages: Computer ScienceComputer Science (R0)