A decision procedure on partially commutative free monoids

DOI10.1016/0166-218X(86)90011-9zbMath0609.20037OpenAlexW2117017961MaRDI QIDQ1086682

A. Massarotti, Aldo De Luca

Publication date: 1986

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(86)90011-9

zbMATH Keywords

algorithmparallel computationcommutation relationsquare-free elementsfinite alphabetpartially commutative free monoidadjacency-listsconcurrency processesnon-commutation relation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Graph theory (including graph drawing) in computer science (68R10) Free semigroups, generators and relations, word problems (20M05) Enumeration in graph theory (05C30) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Unnamed Item
• Square-free words on partially commutative free monoids
• Recognizable subsets of some partially Abelian monoids
• Combinatorial problems of commutation and rearrangements
• An application of the theory of free partially commutative monoids: Asymptotic densities of trace languages