License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSCD.2016.10
URN: urn:nbn:de:0030-drops-59901
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5990/
Go to the corresponding LIPIcs Volume Portal

Avanzini, Martin ; Moser, Georg

Complexity of Acyclic Term Graph Rewriting

pdf-format:
LIPIcs-FSCD-2016-10.pdf (0.6 MB)

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 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.

BibTeX - Entry

@InProceedings{avanzini_et_al:LIPIcs:2016:5990,
  author =	{Martin Avanzini and Georg Moser},
  title =	{{Complexity of Acyclic Term Graph Rewriting}},
  booktitle =	{1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-010-1},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{52},
  editor =	{Delia Kesner and Brigitte Pientka},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5990},
  URN =		{urn:nbn:de:0030-drops-59901},
  doi =		{10.4230/LIPIcs.FSCD.2016.10},
  annote =	{Keywords: Program Analysis, Graph Rewriting, Complexity Analysis}
}

Keywords: Program Analysis, Graph Rewriting, Complexity Analysis
Collection: 1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016)
Issue Date: 2016
Date of publication: 17.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI