The problems of cyclic equality and conjugacy for finite complete rewriting systems (Q1089798)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4005605
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The problems of cyclic equality and conjugacy for finite complete rewriting systems |
scientific article; zbMATH DE number 4005605 |
Statements
The problems of cyclic equality and conjugacy for finite complete rewriting systems (English)
0 references
1986
0 references
It is known that the left-conjugacy problem and the conjugacy problem are decidable for each finite, length-reducing, and complete rewriting system. This does not hold for the problem of cyclic equality as is shown here by presenting a finite, length-reducing, and complete rewriting system with an undecidable problem of cyclic equality. Further, a finite complete rewriting system T is constructed such that the left-conjugacy problem and the conjugacy problem are undecidable for T.
0 references
left-conjugacy problem
0 references
cyclic equality
0 references
finite complete rewriting system
0 references
0.89589155
0 references
0.8925336
0 references
0.88659525
0 references
0.8819522
0 references
0 references
0.87490314
0 references
0.8728065
0 references
0.87220466
0 references
