×

Recognizable subsets of some partially Abelian monoids. (English) Zbl 0559.20040

A free partially abelian monoid S is a monoid which has a finite alphabet A as generating set and in which all laws are of the form ab\(\simeq ba\) for some a,b\(\in S\). Let X be a finite set of words over A each containing all the letters of A at least once. Suppose that the graph the vertices of which are the letters of A and for which the edges correspond to non-commuting pairs of letters of A, is connected. Then the main theorem of the paper states that the subset \([X^*]\) of the free partially abelian monoid \(A^*/\simeq\) containing all the words equivalent to a product of words in X, is rational. Also, it is shown that the set of all words \(u\in A^*\) commuting with a given word \(w\in A^*\) (i.e. wu\(\simeq uw)\) is a rational, finitely generated subset of \(A^*\).
Reviewer: H.Mitsch

MSC:

20M05 Free semigroups, generators and relations, word problems
20M35 Semigroups in automata theory, linguistics, etc.
68Q70 Algebraic theory of languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cartier, P.; Foata, D., Prolèmes combinatoires de commutation et réarrangements, (Lecture Notes in Mathematics, 85 (1969), Springer: Springer Berlin) · Zbl 0186.30101
[2] Clerbout, M.; Latteux, M., Partial commutations and faithful rational transductions, Publication de l’Équipe Lilloise d’Informatique Théorique No IT 54-83 (1983) · Zbl 0548.68073
[3] R. Cori and D. Perrin, Sur la reconnaissabilité dans les monoides partiellement commutatifs libres, RAIRO Inform. Théoret.; R. Cori and D. Perrin, Sur la reconnaissabilité dans les monoides partiellement commutatifs libres, RAIRO Inform. Théoret.
[4] Eilenberg, S., (Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York) · Zbl 0317.94045
[5] Flé, M. P.; Roucairol, G., On serializability of iterated transactions, ACM SIGACT-SIGOPS, 194-200 (1982) · Zbl 0492.68019
[6] Lothaire, M., Combinatorics on Words (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0514.20045
[7] Pin, J.-E., Variétés de Langages Formels (1984), Masson: Masson Paris · Zbl 0636.68093
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.