Semigroups presented by one relation and satisfying the Church-Rosser property (Q1274007)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Semigroups presented by one relation and satisfying the Church-Rosser property |
scientific article |
Statements
Semigroups presented by one relation and satisfying the Church-Rosser property (English)
0 references
11 January 1999
0 references
The author gives a condition for a one-rule semi-Thue system (string rewriting system) \(A\to B\) to be Church-Rosser when the longest self-overlapping of \(A\) is shorter than \(B\). (Reviewer's remark: A necessary and sufficient condition for an arbitrary one-rule system to be Church-Rosser was given in \textit{C. Wrathall} [Confluence of one-rule Thue systems, Lect, Notes Comput. Sci. 572, 237-246 (1992)].
0 references
string rewriting system
0 references