Complexity of Acyclic Term Graph Rewriting

Martin Avanzini 1 Georg Moser 2
1 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
Abstract : Term rewriting has been used as a formal model to reason about the complexity of logic, functional , and imperative programs. In contrast to term rewriting, term graph rewriting permits sharing of common sub-expressions, and consequently is able to capture more closely reasonable implementations of rule based languages. However, the automated complexity analysis of term graph rewriting has received little to no attention. With this work, we provide first steps towards overcoming this situation. We present adap-tions of two prominent complexity techniques from term rewriting, viz, the interpretation method and dependency tuples. Our adaptions are non-trivial, in the sense that they can observe not only term but also graph structures, i.e. take sharing into account. In turn, the developed methods allow us to more precisely estimate the runtime complexity of programs where sharing of sub-expressions is essential.
Type de document :
Communication dans un congrès
Proceedings of FSCD'16, Jun 2016, Porto, Portugal. 〈10.4230/LIPIcs.FSCD.2016〉
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01336582
Contributeur : Martin Avanzini <>
Soumis le : jeudi 23 juin 2016 - 13:04:28
Dernière modification le : samedi 27 janvier 2018 - 01:31:37
Document(s) archivé(s) le : samedi 24 septembre 2016 - 10:35:37

Fichier

proc-avanzini.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Martin Avanzini, Georg Moser. Complexity of Acyclic Term Graph Rewriting. Proceedings of FSCD'16, Jun 2016, Porto, Portugal. 〈10.4230/LIPIcs.FSCD.2016〉. 〈hal-01336582〉

Partager

Métriques

Consultations de la notice

189

Téléchargements de fichiers

44