Remarks on an example of Jantzen (Q793015)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Remarks on an example of Jantzen
scientific article

    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