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.RTA.2013.97
URN: urn:nbn:de:0030-drops-40561
URL: https://drops.dagstuhl.de/opus/volltexte/2013/4056/
Go to the corresponding LIPIcs Volume Portal

Bau, Alexander ; Lohrey, Markus ; Nöth, Eric ; Waldmann, Johannes

Compression of Rewriting Systems for Termination Analysis

pdf-format:
9.pdf (0.5 MB)

Abstract

We adapt the TreeRePair tree compression algorithm and use it as an intermediate step in proving termination of term rewriting systems. We introduce a cost function that approximates the size of constraint systems that specify compatibility of matrix interpretations. We show how to integrate the compression algorithm with the Dependency Pairs transformation. Experiments show that compression reduces running times of constraint solvers, and thus improves the power of automated termination provers.

BibTeX - Entry

@InProceedings{bau_et_al:LIPIcs:2013:4056,
  author =	{Alexander Bau and Markus Lohrey and Eric N{\"o}th and Johannes Waldmann},
  title =	{{Compression of Rewriting Systems for Termination Analysis}},
  booktitle =	{24th International Conference on Rewriting Techniques and Applications (RTA 2013)},
  pages =	{97--112},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-53-8},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{21},
  editor =	{Femke van Raamsdonk},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4056},
  URN =		{urn:nbn:de:0030-drops-40561},
  doi =		{10.4230/LIPIcs.RTA.2013.97},
  annote =	{Keywords: termination of rewriting, matrix interpretations, constraint solving, tree compression}
}

Keywords: termination of rewriting, matrix interpretations, constraint solving, tree compression
Collection: 24th International Conference on Rewriting Techniques and Applications (RTA 2013)
Issue Date: 2013
Date of publication: 24.06.2013

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