Term rewriting has been used as a formal model to reason about the#R##N#complexity of logic, functional, and imperative programs.  In contrast#R##N#to term rewriting, term graph rewriting permits sharing of#R##N#common sub-expressions, and consequently is able to capture more#R##N#closely reasonable implementations of rule based languages.  However,#R##N#the automated complexity analysis of term graph rewriting has received#R##N#little to no attention.#R##N##R##N#With this work, we provide first steps towards overcoming this#R##N#situation. We present adaptions of two prominent complexity techniques#R##N#from term rewriting, viz, the interpretation method and#R##N#dependency tuples.  Our adaptions are non-trivial, in the sense#R##N#that they can observe not only term but also graph structures, i.e.#R##N#take sharing into account. In turn, the developed methods allow us to#R##N#more precisely estimate the runtime complexity of programs where#R##N#sharing of sub-expressions is essential.
['Martin Avanzini', 'Georg Moser']
Complexity of Acyclic Term Graph Rewriting