2026-07-22T20:50:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5990 2024-03-06T10:37:24Z ddc:004 open_access

Complexity of Acyclic Term Graph Rewriting Avanzini, Martin Moser, Georg Program Analysis Graph Rewriting Complexity Analysis 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 adaptions 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Avanzini and Georg Moser 2016 Is Part Of LIPIcs, Volume 52, 1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSCD.2016.10 urn:nbn:de:0030-drops-59901 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2016.10 eng https://creativecommons.org/licenses/by/3.0/legalcode