It is undecidable whether a finite special string-rewriting system presents a group

✍ Scribed by Paliath Narendran; Colm Ó'Dúnlaing; Friedrich Otto

• Publisher: Elsevier Science
• Year: 1991
• Tongue: English
• Weight: 398 KB
• Volume: 98
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(91)90040-9

✦ Synopsis

It is shown that it is undecidable in general whether or not a monoid that is presented by a finite special string-rewriting system is a group. The given proof uses the technique of canonical string-rewriting systems.