A decision procedure on partially commutative free monoids (Q1086682)

Partially commutative free monoids have been considered first by \textit{P. Cartier} and \textit{D. Foata} [Problèmes combinatoires de commutation et réarrangements (Lect. Notes Math. 85) (1969; Zbl 0186.30101)] to deal with some combinatorial problems related to the rearrangements of words. More recently several authors as \textit{A. Bertoni}, \textit{M. Brambilla}, \textit{G. Mauri} and \textit{N. Sabatini} [Mathematical foundations of computer science 1981, Proc. 10th Symp., Strbske Pleso/Czech. 1981, Lect. Notes Comput. Sci. 118, 205--215 (1981; Zbl 0468.68081)] \textit{R. Cori} and \textit{D. Perrin} [RAIRO Inf. Théor. 19, 21--32 (1985; Zbl 0601.68055)] \textit{R. Cori} and \textit{Y. Métivier} [Theor. Comput. Sci. 35, 179--189 (1985; Zbl 0559.20040)] have reconsidered these objects for problems of parallel computation and concurrency processes. The reader should consult the recent overview on this subject by \textit{I. Aalbersberg} and \textit{G. Rozenberg} [Theory of traces, Report 1986, Dept. Comput. Sci., Univ. Leyden, Netherlands]. \(M(A,\theta)\) denotes the partially commutative free monoid relative to the alphabet \(A\) and to the commutation relation \(\theta\) and \(L_2(M(A,\theta))\) the set of all square-free elements of \(M(A,\theta)\). (An element \(m\in M(A,\theta)\) is square-free if \(m\neq rs^2t\), with \(s\neq 1.)\) In \textit{A. Carpi} and \textit{A. de Luca} [Inf. Process. Lett. 22, 125--131 (1986; Zbl 0593.20065)] it has been proved a theorem which gives an algorithm to decide whether the set \(L_2(M(A,\theta))\) is infinite. By means of the graph of the non-commutation relation the above theorem is equivalent to Proposition \(1: L_2(M(A,\theta))\) is infinite if and only if in the graph of the non-commutation relation there exists at least a node of degree \(>2\) or a node of degree 2 having as adjacent nodes still nodes of degree 2. From this result one has that the structure of data which is more convenient to describe the non-commutation graph is the set of adjacency-lists of its nodes. The following result holds: Proposition 2. Given a finite alphabet \(A\) and the set of adjacency-lists of the nodes of the non-commutation graph, one can decide whether \(L_2(M(A,\theta))\) is infinite by an algorithm whose cost (=number of elementary operations) is a linear function of \(\mathrm{Card}(A)\).