2026-07-21T14:16:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2663 2024-03-06T10:33:30Z ddc:004 open_access

Polynomially Bounded Matrix Interpretations Waldmann, Johannes Derivational complexity of rewriting matrix interpretation weighted automata ambiguity of automata finite domain constraints 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Johannes Waldmann 2010 Is Part Of LIPIcs, Volume 6, Proceedings of the 21st International Conference on Rewriting Techniques and Applications (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.RTA.2010.357 urn:nbn:de:0030-drops-26637 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2010.357 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode