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

René Schott 1 Jean-Claude Spehner 2
1 LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 MAGE - Laboratoire de Modélisation et Algorithmique Géométrique
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.
Keywords : Automaton shuffle of words trees
Document type :
Conference papers
Complete list of metadata
https://hal.inria.fr/inria-00000273
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

Identifiers

Collections

INRIA | CNRS | UNIV-LORRAINE | LORIA | SITE-ALSACE

Citation

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⟩

Export

BibTeX TEI DC DCterms EndNote Datacite

Share

Metrics

Record views

53

 

Contact                    Legal Notice                    Personal Data