LIPIcs.RTA.2010.357.pdf
- Filesize: 199 kB
- 16 pages
Document
Polynomially Bounded Matrix Interpretations
Author
-
Part of:
Volume:
Proceedings of the 21st International Conference on Rewriting Techniques and Applications (RTA 2010)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Rewriting Techniques and Applications (RTA) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2010-07-06
Cite AsGet BibTex
Johannes Waldmann. Polynomially Bounded Matrix Interpretations. In Proceedings of the 21st International Conference on Rewriting Techniques and Applications. Leibniz International Proceedings in Informatics (LIPIcs), Volume 6, pp. 357-372, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/LIPIcs.RTA.2010.357
https://doi.org/10.4230/LIPIcs.RTA.2010.357
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.
Keywords
- Derivational complexity of rewriting
- matrix interpretation
- weighted automata
- ambiguity of automata
- finite domain constraints
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads