Termination of Cycle Rewriting


Hans Zantema, Barbara König, and H.J. Sander Bruggink. Termination of cycle rewriting. In Proceedings of RTA-TLCA 2014, 2014.


String rewriting can not only be applied on strings, but also on cycle 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, arctic matrices and tropical matrices can be applied. Further we show how any terminating string rewriting system can be transformed to a terminating cycle rewriting system, preserving derivational complexity.

Suggested BibTeX entry:

    author = {Hans Zantema and Barbara K{\"o}nig and H.J. Sander Bruggink},
    booktitle = {Proceedings of RTA-TLCA 2014},
    title = {Termination of Cycle Rewriting},
    year = {2014}

This work is not available online here.
© University of Duisburg-Essen, Theoretical Computer Science group