Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2010.357
URN: urn:nbn:de:0030-drops-26637
URL: https://drops.dagstuhl.de/opus/volltexte/2010/2663/
Waldmann, Johannes
Polynomially Bounded Matrix Interpretations
| pdf-format: |
|
Abstract
Matrix interpretations can be used to bound the derivational complexity of rewrite systems. We present a criterion that completely characterizes matrix interpretations that are polynomially bounded. It includes the method of upper triangular interpretations as a special case, and we prove that the inclusion is strict. The criterion can be expressed as a finite domain constraint system.It translates to a Boolean constraint system with a size that is polynomial in the dimension of the interpretation. We report on performance of an implementation.
BibTeX - Entry
@InProceedings{waldmann:LIPIcs:2010:2663,
author = {Johannes Waldmann},
title = {{Polynomially Bounded Matrix Interpretations}},
booktitle = {Proceedings of the 21st International Conference on Rewriting Techniques and Applications},
pages = {357--372},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-18-7},
ISSN = {1868-8969},
year = {2010},
volume = {6},
editor = {Christopher Lynch},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2663},
URN = {urn:nbn:de:0030-drops-26637},
doi = {10.4230/LIPIcs.RTA.2010.357},
annote = {Keywords: Derivational complexity of rewriting, matrix interpretation, weighted automata, ambiguity of automata, finite domain constraints}
}
| Keywords: | Derivational complexity of rewriting, matrix interpretation, weighted automata, ambiguity of automata, finite domain constraints | |
| Seminar: | Proceedings of the 21st International Conference on Rewriting Techniques and Applications | |
| Issue date: | 2010 | |
| Date of publication: | 06.07.2010 |
