Homogeneous Thue systems and the Church-Rosser property (Q798317)

From MaRDI portal





scientific article; zbMATH DE number 3869311
Language Label Description Also known as
default for all languages
No label defined
    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
      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

      Identifiers