Termination of cycle rewriting

H. Zantema, B. König, H.J.S. Bruggink

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)
2 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publicationRewriting and Typed Lambda Calculi (Joint International Conference, RTA-TLCA 2014, Vienna, Austria, July 14-17, 2014. Proceedings)
EditorsG. Dowek
Place of PublicationBerlin
PublisherSpringer
Pages476-490
ISBN (Print)978-3-319-08917-1
DOIs
Publication statusPublished - 2014
Eventconference; Joint International Conferenc on Rewriting and Typed Lambda Calculi; 2014-07-14; 2014-07-17 -
Duration: 14 Jul 201417 Jul 2014

Publication series

NameLecture Notes in Computer Science
Volume8560
ISSN (Print)0302-9743

Conference

Conferenceconference; Joint International Conferenc on Rewriting and Typed Lambda Calculi; 2014-07-14; 2014-07-17
Period14/07/1417/07/14
OtherJoint International Conferenc on Rewriting and Typed Lambda Calculi

Cite this