Transforming cycle rewriting into string rewriting

D. Sabel, H. Zantema

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

3 Citaten (Scopus)
2 Downloads (Pure)


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.
Originele taal-2Engels
TitelRewriting Techniques and Applications (26th International Conference, RTA'15, Warsaw, Poland, June 29-July 3, 2015)
RedacteurenM. Fernández
Plaats van productieDagstuhl
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN van geprinte versie978-3-939897-85-9
StatusGepubliceerd - 2015

Publicatie series

NaamLIPIcs: Leibniz International Proceedings in Informatics
ISSN van geprinte versie1868-8968


Duik in de onderzoeksthema's van 'Transforming cycle rewriting into string rewriting'. Samen vormen ze een unieke vingerafdruk.

Citeer dit