| HAL-Inria | Publications, software ... of Inria's scientists |
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.
https://hal.inria.fr/inria-00000273
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
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
