Abstract
We present a single-axiom. Thue system with a decidable word problem for which there does not exist any finite equivalent canonical system. However, an equivalent finite canonical system for this Thue system can be obtained if new symbols are introduced in the presentation. This result settles an open question by Jantzen (1982) who asked whether every Thue system with a decidable word problem has an equivalent finite canonical system. We also discuss relationships between Thue systems and term rewriting systems.
| Original language | English |
|---|---|
| Pages (from-to) | 337-344 |
| Number of pages | 8 |
| Journal | Theoretical Computer Science |
| Volume | 35 |
| Issue number | C |
| DOIs | |
| State | Published - 1985 |
Keywords
- Church-Rosser property
- Thue systems
- canonical systems
- semi-Thue systems
- term rewriting systems
- word problem
Fingerprint
Dive into the research topics of 'A finite thue system with decidable word problem and without equivalent finite canonical system'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver