Some properties of finite special string-rewriting systems

✍ Scribed by Louxin Zhang

• Book ID: 103918609
• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 567 KB
• Volume: 14
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1016/0747-7171(92)90012-s

✦ Synopsis

This paper investigates decision problems of finite, special string-rewriting systems . There are two main results . The first one is that the word problem for a finite, special string-rewriting system T on alphabet A is reducible to its restricted version: given a word w, is w congruent to any fixed element z on A? Another is a Markov type theorem : a property P is undecidable for finite, special string-rewriting systems if P implies any fixed Markov property of finitely presented special monoids and there exists a finite, special string-rewriting system R on alphabet C with the property that a finite, special string-rewriting system T on A has P whenever M(A ;T) is isomorphic to M(C ; R) .