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
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