Remarks on an example of Jantzen (Q793015)

From MaRDI portal





scientific article; zbMATH DE number 3855084
Language Label Description Also known as
default for all languages
No label defined
    English
    Remarks on an example of Jantzen
    scientific article; zbMATH DE number 3855084

      Statements

      Remarks on an example of Jantzen (English)
      0 references
      0 references
      1984
      0 references
      The paper presents an alternative proof of a theorem of Jantzen to the effect that the monoid J presented by the one rule (abbaab,1) is Church- Rosser. The author's introduction notes ''Book showed that if S is a finite monadic Church-Rosser Thue system, then every congruence class is a deterministic context-free language... Jantzen showed that the condition Church-Rosser could not be left out, even for one-rule special Thue systems, for he showed that his example has the property that no congruence class is a context free language and that there is no equivalent Church-Rosser Thue system on \(\{\) a,\(b\}\).'' In the current paper, an alternate presentation of J which solves the word problem is given. ''... we construct an equivalent infinite Thue system which is locally confluent but not noetherian... the equivalent system can be used to generate an algorithm which produced a unique normal form for each word; furthermore, two words are congruent if and only if they have the same normal form... [the] result is established by transforming the original monoid which has two generators, into a four generator monoid for which the corresponding Thue system can be extended to an infinite locally confluent and noetherian system.''
      0 references
      monoid
      0 references
      Church-Rosser Thue system
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references