Words over a partially commutative alphabet. (English) Zbl 0602.68070

Combinatorial algorithms on words, Proc. NATO Adv. Res. Workshop, Maratea/Italy 1984, NATO ASI Ser., Ser. F 12, 329-340 (1985).
[For the entire collection see Zbl 0564.00027.]
In this paper the author presents a survey of results obtained on commutation methods based on some previous results of the literature. First, terminology and definitions are introduced. We remind here the central notions: If A is a finite alphabet and \(\theta\) a binary relation on A (\(\theta\) is supposed to be symmetric), then for two letters a,b\(\in A\) the relation ab\(\equiv ba\) means that the pair (a,b) is in relation \(\theta\). By considering the congruence on \(A^*\) generated by this relation it is written \(u\equiv v mod \theta\) if the two words u, v are congruent. This means that there exist words \(w_ 0,w_ 1,...,w_ k\) with \(w_ 0=u\), \(w_ k=v\) and for each j (0\(\leq j\leq k-1)\), \(w_ j=r_ jabs_ j\), \(w_{j+1}=r_ jbas_ j\) with (a,b)\(\in \theta\). The quotient of \(A^*\) by the congruence \(\equiv\), denoted by M(A,\(\theta)\) is called the free partially commutative monoid generated by A with respect to the relation \(\theta\). Such a monoid is also called a commutation monoid.
Then, two normal form theorems in commutation monoids are discussed, the first one being due to D. Foata and the second one to D. Knuth. Algorithms for computing such normal forms of the words are also explained by the author, and some examples illustrating these discussions are given, too. In the third section some results on the structure of commutation monoids are presented and in the last one the problem of recognizability in commutation monoids is studied.
Reviewer: G.Orman


68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.


Zbl 0564.00027