Thue systems and the Church-Rosser property. (English) Zbl 0553.03025

Mathematical foundations of computer science, Proc. 11th Symp., Praha/Czech. 1984, Lect. Notes Comput. Sci. 176, 80-95 (1984).
[For the entire collection see Zbl 0544.00022.]
This work gives a condensed survey of many results about string transformation systems and the Church-Rosser property. Due to the lack of space, some of the results are formulated quite short and all of them without proof. The work focusses on sequential string rewriting and distinguishes confluent semi-Thue systems (STS) that terminate by length from those which are Church-Rosser in the original sense and terminate by a different reason, hence represent some confluent and Noetherian rewriting relation. This distinction has not been made in previous work on STS’s, even not by the author himself.
Except of referencing known results, there are formulated quite new results about a whole class of STS’s \(S_ n:=\{((ab)^ nba,\lambda)\},\) \(n\geq 1\), all of which present monoids that are in fact groups called \(G_ n\cong <a,b;(ab)^ nba=1>.\) For \(n\geq 2\) these groups share almost all properties obtained for the Jantzen monoid presented by the special one-relator STS \(S=\{(abbaab,\lambda)\}.\) Only the STS \(S_ 1\) does not fit well into this sequence and in the paper it was inaccurately used as an example. The author later has been able to show that \(S_ 1\) cannot have any equivalent uniquely terminating (i.e. complete) STs, thus turning this careless statement into a positive result.


03D03 Thue and Post systems, etc.
68Q65 Abstract data types; algebraic specification
03C05 Equational classes, universal algebra in model theory


Zbl 0544.00022