On termination of confluent one-rule string-rewriting systems

✍ Scribed by Kayoko Shikishima-Tsuji; Masashi Katsura; Yuji Kobayashi

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 507 KB
• Volume: 61
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(96)00200-1

✦ Synopsis

The termination of a confluent one-rule string-rewriting system R = (s + I} is reduced to that of another one-rule system K = {s' -B t') such that s' is self-overlap-free &of). A necessary and sufficient condition is given for termination of a one-rule system R = {s --+ t} such that s is sof and s overlaps r once on both sides. 0 1997 Elsevier Science B.V.