String rewriting can not only be applied on strings, but also on cycles and even on general graphs. In this paper we investigate termination of string rewriting applied on cycles, shortly denoted as cycle rewriting, which is a strictly stronger requirement than termination on strings. Most techniques for proving termination of string rewriting fail for proving termination of cycle rewriting, but match bounds and some variants of matrix interpretations can be applied. Further we show how any terminating string rewriting system can be transformed to a terminating cycle rewriting system, preserving derivational complexity.
|Name||Lecture Notes in Computer Science|
|Conference||conference; Joint International Conferenc on Rewriting and Typed Lambda Calculi; 2014-07-14; 2014-07-17|
|Period||14/07/14 → 17/07/14|
|Other||Joint International Conferenc on Rewriting and Typed Lambda Calculi|