A decision procedure on partially commutative free monoids
type: Item
instance of: scholarly article
title: A decision procedure on partially commutative free monoids
zbMATH Open document ID: 0609.20037
DOI: 10.1016/0166-218X(86)90011-9
author: A. Massarotti
author: Aldo De Luca
published in: Discrete Applied Mathematics
publication date: 1986-01-01T00:00:00Z
review text: 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-commutati…
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C30
zbMATH DE Number: 3985517
zbMATH Keywords: parallel computation
zbMATH Keywords: concurrency processes
zbMATH Keywords: partially commutative free monoid
zbMATH Keywords: commutation relation
zbMATH Keywords: square-free elements
zbMATH Keywords: algorithm
zbMATH Keywords: non-commutation relation
zbMATH Keywords: finite alphabet
zbMATH Keywords: adjacency-lists
MaRDI profile type: Publication
cites work: An application of the theory of free partially commutative monoids: Asymptotic densities of trace languages
cites work: Square-free words on partially commutative free monoids
cites work: Combinatorial problems of commutation and rearrangements
cites work: Recognizable subsets of some partially Abelian monoids
cites work: Q3736919
full work available at URL: 0166-218x(86)90011-9
OpenAlex ID: W2117017961
description: scientific article; zbMATH DE number 3985517