HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Wednesday, September 21, 2005 - 4:45:09 PM
Last modification on : Saturday, October 16, 2021 - 11:26:08 AM




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