Automates et commutations partielles. (Automata and partial commutations). (French) Zbl 0601.68055

We consider words over an alphabet equipped with a partial commutation rule. The main result of the paper gives a sufficient condition for a set of words closed under the commutation rule to be recognizable by a finite automaton. More precisely, if X is recognizable and if ab\(\sim ba\) implies that the letters a and b do not appear in the same word of X, then the closure of \(X^*\) under the commutation rule is recognizable.


68Q45 Formal languages and automata
20M05 Free semigroups, generators and relations, word problems
20M35 Semigroups in automata theory, linguistics, etc.
Full Text: EuDML


[1] 1. P. CARTIER et D. FOATA, Problèmes combinatoires de commutation et réarrangements, Lecture Notes in Math., n^\circ 85, 1969, Springer Verlag. Zbl0186.30101 MR239978 · Zbl 0186.30101
[2] 2. S. EILENBERG, Automata, Languages and Machines, vol. A, 1974, Academic Press. Zbl0317.94045 MR530382 · Zbl 0317.94045
[3] 3. M. P. FLÉ et G. ROUCAIROL, On Serializability of Iterated Transaction, A.C.M. SIGACT-SIGOPS, 1982, p. 194-200.
[4] 4. M. LOTHAIRE, Combinatorics on Words, 1983, Addison Wesley. Zbl0514.20045 MR675953 · Zbl 0514.20045
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.