Skip to Main content Skip to Navigation
Conference papers

On the Minimal Automaton of the Shuffle of Words and Araucarias

Abstract : The shuffle of k words u1,..., uk is the set of words obtained by interleaving the letters of these words such that the order of appearance of all letters of each word is respected. The study of the shuffle product of words leads to the construction of an automaton whose structure is deeply connected to a family of trees which we call araucarias. We prove many structural properties of this family of trees and give some combinatorial results. The link with the minimal partial automaton which recognizes the words of the shuffle is established. Our method works for the shuffle of k > 2 words.
Document type :
Conference papers
Complete list of metadata
Contributor : Agnès Vidard <>
Submitted on : Wednesday, September 21, 2005 - 4:45:09 PM
Last modification on : Tuesday, April 24, 2018 - 1:30:55 PM

Links full text




René Schott, Jean-Claude Spehner. On the Minimal Automaton of the Shuffle of Words and Araucarias. 4th International Conference on Machines, Computations and Universality - MCU 2004, Sep 2004, Saint Petersburg, Russia, pp.316-327, ⟨10.1007/b106980⟩. ⟨inria-00000273⟩



Record views