The Church-Rosser property and special Thue systems (Q1071759): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Paliath Narendran / rank | |||
Property / author | |||
Property / author: Robert McNaughton / rank | |||
Property / author | |||
Property / author: Paliath Narendran / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Robert McNaughton / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(85)90134-3 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2053388467 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on special thue systems with a single defining relation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Testing for the Church-Rosser property / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3319767 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5686240 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4529547 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Church-Rosser property and special Thue systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4105657 / rank | |||
Normal rank |
Latest revision as of 12:56, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The Church-Rosser property and special Thue systems |
scientific article |
Statements
The Church-Rosser property and special Thue systems (English)
0 references
1985
0 references
In an earlier paper [ibid. 35, 109-114 (1985; Zbl 0563.03018)] we gave an \(O(| T|^ 3)\) algorithm for testing the Church-Rosser property of Thue systems, where \(| T|\) is the total size of the Thue system. Here we improve that bound to O(k\(| T|)\), where k is the number of rules in T, in the case when the Thue system is special, i.e., when all its rules are of the form (x,\(\lambda)\) where \(\lambda\) is the empty string. Also obtained are several results on special Thue systems which may be of independent interest.
0 references
word equation
0 references
pattern matching
0 references
complexity bound
0 references
algorithm for testing the Church-Rosser property
0 references