It is undecidable whether a finite special string-rewriting system presents a group
From MaRDI portal
Publication:1184861
DOI10.1016/0012-365X(91)90040-9zbMath0749.20032MaRDI QIDQ1184861
Colm P. O'Dunlaing, Friedrich Otto, Paliath Narendran
Publication date: 28 June 1992
Published in: Discrete Mathematics (Search for Journal in Brave)
20M05: Free semigroups, generators and relations, word problems
68Q42: Grammars and rewriting systems
20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
Related Items
On the descriptive power of special Thue systems, Completing a finite special string-rewriting system on the congruence class of the empty word, Some properties of finite special string-rewriting systems, The word problem for one-relation monoids: a survey
Cites Work