Thue systems as rewriting systems.

*(English)*Zbl 0587.03026
Rewriting techniques and applications, 1st Int. Conf., Dijon/France 1985, Lect. Notes Comput. Sci. 202, 63-94 (1985).

[For the entire collection see Zbl 0568.00022.]

We consider an alphabet \(\Sigma\), a Thue system \(T\subset \Sigma^*\times \Sigma^*\) and the Thue congruence \(\leftrightarrow^{*}\) generated by T. We know that T can be viewed as a rewriting system if we consider the pairs (u,v)\(\in T\) as rewriting rules, and as a monoid presentation of the monoid \(M_ T=\Sigma^*/\leftrightarrow^{*}\). The paper under review studies the decidability and the complexity of the word problem for noetherian and confluent rewriting systems and presents algebraic properties of monoids with presentations that are Church-Rosser. A very nice example from algebraic protocols shows the usefulness of the notion of reduction based on the length. Recall that the reduction relation based on the length \(\to\) is defined as follows: \(x\to y\) if \(x\leftrightarrow^{*}y\) and \(| x| >| y|\). A section of the paper presents several properties of arbitrary Thue systems and Thue systems with the Church- Rosser property. A more complete list of these properties can be found in ”Thue systems and the Church-Rosser property: replacement systems, specification of formal languages, and presentations of monoids” [Combinatorics on words. Progress and perspectives, Proc. Int. Meet., Waterloo/Can. 1982, 1-38 (1983; Zbl 0563.68062)] of the same author. The results are presented without proofs but many helpful comments give ideas for future work.

We consider an alphabet \(\Sigma\), a Thue system \(T\subset \Sigma^*\times \Sigma^*\) and the Thue congruence \(\leftrightarrow^{*}\) generated by T. We know that T can be viewed as a rewriting system if we consider the pairs (u,v)\(\in T\) as rewriting rules, and as a monoid presentation of the monoid \(M_ T=\Sigma^*/\leftrightarrow^{*}\). The paper under review studies the decidability and the complexity of the word problem for noetherian and confluent rewriting systems and presents algebraic properties of monoids with presentations that are Church-Rosser. A very nice example from algebraic protocols shows the usefulness of the notion of reduction based on the length. Recall that the reduction relation based on the length \(\to\) is defined as follows: \(x\to y\) if \(x\leftrightarrow^{*}y\) and \(| x| >| y|\). A section of the paper presents several properties of arbitrary Thue systems and Thue systems with the Church- Rosser property. A more complete list of these properties can be found in ”Thue systems and the Church-Rosser property: replacement systems, specification of formal languages, and presentations of monoids” [Combinatorics on words. Progress and perspectives, Proc. Int. Meet., Waterloo/Can. 1982, 1-38 (1983; Zbl 0563.68062)] of the same author. The results are presented without proofs but many helpful comments give ideas for future work.

Reviewer: D.Lucanu

##### MSC:

03D03 | Thue and Post systems, etc. |

03D40 | Word problems, etc. in computability and recursion theory |

20M05 | Free semigroups, generators and relations, word problems |

68Q65 | Abstract data types; algebraic specification |