It is undecidable whether a finite special string-rewriting system presents a group (Q1184861): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: When is a monoid a group? The Church-Rosser case is tractable / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a special monoid with a single defining relation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On monoids presented by a single relation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3853827 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5804999 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On deciding whether a monoid is a free monoid or is a group / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Systems of reductions / rank | |||
Normal rank |
Latest revision as of 16:13, 15 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | It is undecidable whether a finite special string-rewriting system presents a group |
scientific article |
Statements
It is undecidable whether a finite special string-rewriting system presents a group (English)
0 references
28 June 1992
0 references
Let \(G=(\Sigma;R)\) be a finitely presented (f.p.) group with undecidable word problem, \(w\in\Sigma^*\), \(G(w)=(\Sigma\cup\{a,b\}\); \(R\), \(awbbaab=1\)) be a f.p. (special) semigroup. It is shown that \(G(w)\) is a group iff \(w=1\) in \(G\). This gives the theorem formulated in the title.
0 references
finitely presented special semigroups
0 references
finitely presented group
0 references
word problem
0 references