2026-08-17T01:14:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5203 2024-03-06T10:36:03Z ddc:004 open_access

Transforming Cycle Rewriting into String Rewriting Sabel, David Zantema, Hans rewriting systems string rewriting termination We present new techniques to prove termination of cycle rewriting, that is, string rewriting on cycles, which are strings in which the start and end are connected. Our main technique is to transform cycle rewriting into string rewriting and then apply state of the art techniques to prove termination of the string rewrite system. We present three such transformations, and prove for all of them that they are sound and complete. Apart from this transformational approach, we extend the use of matrix interpretations as was studied before. We present several experiments showing that often our new techniques succeed where earlier techniques fail. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Sabel and Hans Zantema 2015 Is Part Of LIPIcs, Volume 36, 26th International Conference on Rewriting Techniques and Applications (RTA 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.RTA.2015.285 urn:nbn:de:0030-drops-52032 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2015.285 eng https://creativecommons.org/licenses/by/3.0/legalcode