Homogeneous Thue systems and the Church-Rosser property (Q798317)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Homogeneous Thue systems and the Church-Rosser property |
scientific article; zbMATH DE number 3869311
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Homogeneous Thue systems and the Church-Rosser property |
scientific article; zbMATH DE number 3869311 |
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