Homogeneous Thue systems and the Church-Rosser property (Q798317)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Homogeneous Thue systems and the Church-Rosser property |
scientific article |
Statements
Homogeneous Thue systems and the Church-Rosser property (English)
0 references
1984
0 references
A Thue system T is a subset of \(\Sigma^*\times\Sigma^*\) (\(\Sigma\) being a finite set and \(\Sigma^*\) the free monoid with identity 1 generated by \(\Sigma)\). A Thue system T is special if \(T\subseteq\Sigma^*\times\{1\},\) is homogeneous if there is k such that \((w,1)\in T\) implies that the length of w is k. It is proved that a finite homogeneous Thue system is either Church-Rosser or there is no Church-Rosser Thue system equivalent to T. Further, groups of units in monoids generated by Thue systems \(T=\{(w,1)\}\) are treated.
0 references
Church-Rosser property
0 references
monoid presented by a Thue system
0 references
finite homogeneous Thue system
0 references