×

Termination of string rewriting rules that have one pair of overlaps. (English) Zbl 1038.68065

Nieuwenhuis, Robert (ed.), Rewriting techniques and applications. 14th international conference, RTA 2003, Valencia, Spain, June 9–11, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40254-3/pbk). Lect. Notes Comput. Sci. 2706, 410-423 (2003).
Summary: This paper presents a partial solution to the long standing open problem whether termination of one-rule string rewriting is decidable. Overlaps between the two sides of the rule play a central role in existing termination criteria. We characterize termination of all one-rule string rewriting systems that have one such overlap at either end. This both completes a result of Kurth and generalizes a result of Shikishima-Tsuji et al.
For the entire collection see [Zbl 1029.00060].

MSC:

68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite
Full Text: Link