On regular trace languages. (English) Zbl 0634.68076

Let A be a finite alphabet and let r be a symmetrical relation on A. Let us consider the free partially commutative monoid M(A,r) generated by A with respect to r (i.e., the quotient of A * by the congruence relation generated by (ab,ba) for all (a,b) in r). It is proved that the free partially commutative monoids M(A,r) whose regular sets form a Boolean algebra or are all unambiguous are the free products of free commutative monoids.
Reviewer: A.Stolboushkin


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


Full Text: DOI


[1] IJ.J. Aalbersberg and E. Welzl, Trace languages defined by regular string languages, RAIRO Inform. Théor., to appear. · Zbl 0612.68071
[2] Aalbersberg, IJ.J.; Rozenberg, G., Theory of traces, ()
[3] Benois, M., Parties rationnelles du groupe libre, C.R. acad. sci. Paris Sér. A, 269, 1188-1190, (1969) · Zbl 0214.03903
[4] Berstel, J., Transductions and context-free languages, (1979), Teubner Stuttgart · Zbl 0424.68040
[5] Bertoni, A.; Mauri, G.; Sabadini, N., Equivalence and membership problems for regular trace languages, (), 61-71 · Zbl 0486.68079
[6] Bertoni, A.; Mauri, G.; Sabadini, N., Unambiguous regular trace languages, () · Zbl 0627.68060
[7] Cartier, P.; Foata, D., Problèmes combinatoires de commutations et Réarrangements, () · Zbl 0186.30101
[8] Conway, J.H., Regular algebra and finite machines, (1971), Chapman and Hall London · Zbl 0231.94041
[9] Cori, R.; Perrin, D., Automates et commutations partielles, RAIRO inform. théor., 19, 21-32, (1985) · Zbl 0601.68055
[10] Cori, R.; Métivier, Y., Recognizable subsets of some partially abelian monoids, Theoret. comput. sci., 35, 179-189, (1985) · Zbl 0559.20040
[11] Eilenberg, S., Automata, languages and machines, Vol. A, (1974), Academic Press New York/London · Zbl 0317.94045
[12] Eilenberg, S.; Schützenberger, M.P., Rational sets in commutative monoids, J. algebra, 13, 344-353, (1969) · Zbl 0206.02703
[13] Flé, M.P.; Roucairol, G., Maximal serializability of iterated transactions, Theoret. comput. sci., 38, 1-16, (1985) · Zbl 0572.68082
[14] Fliess, M., Deux applications de la représentation matricielle d’une série rationnelle non commutative, J. algebra, 19, 344-353, (1971) · Zbl 0222.16001
[15] Ginsburg, S.; Spanier, E.H., Bounded ALGOL-like languages, Trans. amer. math. soc., 113, 333-368, (1964) · Zbl 0142.24803
[16] Lothaire, M., Combinatorics on words, () · Zbl 1001.68093
[17] Mazurkiewicz, A., Traces, histories, and graphs: instances of a process monoid, (), 115-133
[18] Metivier, Y., Une condition suffisante de reconnaissabilité dans un monoïde partiellement commutatif, RAIRO inform. théor., 20, 121-127, (1986) · Zbl 0599.20107
[19] Ochmanski, E., Regular behaviour of concurrent systems, EATCS bulletin 27, (October 1985)
[20] Perrin, D., Words over partially commutative alphabet, (), 329-340
[21] Reutenauer, Ch., Sur LES semi-groupes vérifiant le théorème de Kleene, RAIRO inform. théor., 19, 281-291, (1985) · Zbl 0575.20055
[22] J. Sakarovitch, Sur les parties rationnelles d’un produit libre, to appear.
[23] Ullman, J., Principle of database systems, (1980), Computer Science Press Rockville, MD
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.