Affiliations: Istituto di Scienza e Tecnologie dell'Informazione "A.
Faedo", CNR, Via G. Moruzzi 1, 56124 Pisa, Italy.
maurice.terbeek@isti.cnr.it | Leiden Institute of Advanced Computer Science,
Universiteit Leiden, P.O. Box 9512, 2300 RA Leiden, The Netherlands.
kleijn@liacs.nl
Note: [] Address for correspondence: Istituto di Scienza e Tecnologie
dell'Informazione "A. Faedo", CNR, Via G. Moruzzi 1, 56124 Pisa, Italy
Abstract: Motivated by different ways to obtain team automata from
synchronizing component automata, we consider various definitions of
synchronized shuffles of words. A shuffle of two words is an interleaving of
their symbol occurrenceswhich preserves the original order of these occurrences
within each of the two words. In a synchronized shuffle, however, also two
occurrences of one symbol, each from a different word, may be identified as a
single occurrence. In case at least one of the words involved is infinite, a
(synchronized) shuffle can also be unfair in the sense that an infinite word
may prevail fromsome point onwards even when the other word still has
occurrences to contribute to the shuffle. We prove that for the synchronized
shuffle operations under consideration, every (fair or unfair) synchronized
shuffle can be obtained as a limit of synchronized shuffles of the finite
prefixes of the words involved. In addition, it is shown that with the
exception of one, all synchronized shuffle operations that we consider satisfy
a natural notion of associativity, also in case of unfairness. Finally, using
these results, some compositionality results for team automata are established.
Keywords: Team automata, synchronized shuffling, infinite words, fairness, associativity, compositionality
