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
    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
    0 references
    0 references
    0 references
    0 references
    Church-Rosser property
    0 references
    monoid presented by a Thue system
    0 references
    finite homogeneous Thue system
    0 references