Cori, Robert; Perrin, Dominique Automates et commutations partielles. (Automata and partial commutations). (French) Zbl 0601.68055 RAIRO, Inf. Théor. 19, 21-32 (1985). 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. Cited in 3 ReviewsCited in 79 Documents MSC: 68Q45 Formal languages and automata 20M05 Free semigroups, generators and relations, word problems 20M35 Semigroups in automata theory, linguistics, etc. Keywords:closure; recognition; partial commutation rule; finite automaton PDFBibTeX XMLCite \textit{R. Cori} and \textit{D. Perrin}, RAIRO, Inf. Théor. 19, 21--32 (1985; Zbl 0601.68055) Full Text: EuDML References: [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 · doi:10.1007/BFb0079468 [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. 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.