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

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)

zbMATH Keywords

word problemfinitely presented groupfinitely presented special semigroups

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Grammars and rewriting systems (68Q42) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (4)

On the descriptive power of special Thue systems ⋮ The word problem for one-relation monoids: a survey ⋮ Completing a finite special string-rewriting system on the congruence class of the empty word ⋮ Some properties of finite special string-rewriting systems

Cites Work

• Unnamed Item
• Unnamed Item
• On deciding whether a monoid is a free monoid or is a group
• Systems of reductions
• On a special monoid with a single defining relation
• When is a monoid a group? The Church-Rosser case is tractable
• On monoids presented by a single relation

This page was built for publication: It is undecidable whether a finite special string-rewriting system presents a group