✦ LIBER ✦
Almost all one-rule thue systems have decidable word problems
✍ Scribed by Ronald V Book; Craig C Squier
- Publisher
- Elsevier Science
- Year
- 1984
- Tongue
- English
- Weight
- 167 KB
- Volume
- 49
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
The decidability of the word problem for one-rule Thue systems is an open cluestion. In the case of one-rule special Thue systems, i.e., those of the form {(w, 1)} where 1 is the identity, it is known [1] that the word problem is decidable.
Here we show that 'almost all' one-rule Thue systems have decidable word problems, where the notion of 'almost all' expresses a density condition.
If ~ is a finite alphabet, then ~* is the free monoid with identity 1 generated by ~.