The undecidability of the preperfectness of Thue systems (Q797574): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Confluent and Other Types of Thue Systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Homogeneous Thue systems and the Church-Rosser property / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Testing for the Church-Rosser property / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Une généralisation des ensembles de Dyck / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3862379 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5812175 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Infinite regular Thue systems / rank | |||
Normal rank |
Latest revision as of 13:37, 14 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The undecidability of the preperfectness of Thue systems |
scientific article |
Statements
The undecidability of the preperfectness of Thue systems (English)
0 references
1984
0 references
Thue systems are string replacement systems that present monoids. Since the word problem for them was proved to be undecidable by Post and Markov in the 1940's, there has been some interest in developing conditions under which the word problem is decidable. A hierarchy of three has been defined: Church-Rosser systems are properly included in almost-confluent systems, which are properly included in preperfect systems. At present it is possible to decide whether a finite Thue system is almost-confluent or Church-Rosser, but testing for preperfectness has been an open problem for years. Here we prove that it is undecidable, by reducing it to the emptiness problem for deterministic linear-bounded automata (DLBA's).
0 references
Thue systems
0 references
string replacement systems
0 references
monoids
0 references
Church-Rosser systems
0 references
almost-confluent systems
0 references
preperfect systems
0 references
emptiness problem for deterministic linear-bounded automata
0 references