Shuffle of Words and Araucaria Trees

• Autorzy: Schott R. , Spehner J-C.
• Języki publikacji: EN

Abstrakty

EN

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. We introduce a family of remarkable symmetrical polynomials which play a crucial role in the computation of the size of the araucarias. We prove that the minimal partial automaton which recognizes the shuffle of a finite number of special words contains an araucaria for each integer k > 0.

Słowa kluczowe

EN

automation; shuffle of words; remarkable polynomials; trees

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 74, nr 4
• Strony: 579--601
• Opis fizyczny: bibliogr. 18 poz., wykr.

Twórcy

autor

Schott R.

autor

Spehner J-C.

• Laboratoire MIA, Equipe MAGE, FST, Université de Haute Alsace, 68093, Mulhouse, France,

Bibliografia

• [1] Allauzen C., Calcul efficace du shuffle de k mots, Prépublication de l'Institut Gaspard Monge, 36, 2000.
• [2] Berstel J. and Boasson L., Shuffle factorization is unique, Theoretical Computer Science, 273, 2002, 47-67.
• [3] Cori R. and Perrin D., Automates et commutations partielles, RAIRO Inf. Theor., 19, 1985, 21-32.
• [4] Diekert V., Combinatorics of traces, Lecture Notes in Computer Science, 454, Springer Verlag, 1990.
• [5] Eilenberg S., Automata, Languages and Machines, Academic Press, 1974.
• [6] Franc¸on J., Une approche quantitative de l'exclusion mutuelle, Theoretical Informatics and Applications, 20, 3, 1986, 275-289.
• [7] Gómez A. C. and Pin J.-E., On a conjecture of Schnoebelen, Lecture Notes in Computer Science, 2710, 2003, 35-54.
• [8] Lothaire M., Combinatorics on words, Addison-Wesley, Reading, MA, 1982.
• [9] Mateescu A., Shuffle of !-words: algebraic aspects, Proceedings of STACS 98, Lecture Notes in Computer Science, 1373, 150-160, Springer Verlag 1998.
• [10] NivatM., Ramkumar G.D.S., Pandu Rangan C., Saoudi A., and SundaramR., Efficient parallel shuffle recognition, Parallel Processing Letters, 4, 1994, 455-463.
• [11] Pradeep B. and Siva Ram Murthy C., A constant time string shuffle algorithm on reconfigurable meshes, Internat. J. Comput. Math., 68, 1998, 251-259.
• [12] Radford D. E., A natural ring basis for the shuffle algebra and an application to group schemes, J. Algebra, 58, 1979, 432-454.
• [13] Schnoebelen P., Decomposable regular languages and the shuffle operator, EATCS Bull., 67, 1999, 283-289.
• [14] Schott R. and Spehner J.-C., Efficient generation of commutation classes, Journal of Computing and Information, 2, 1, 1996, 1028-1045. Special issue: Proceedings of Eighth International Conference of Computing and Information (ICCI'96), Waterloo, Canada, June 19-22, 1996.
• [15] Schott R. and Spehner J.-C., Two optimal parallel algorithms on the commutation class of a word, Theoretical Computer Science, 324, 2004, 107-131.
• [16] Schott R. and Spehner J.-C., On the minimal automaton of the shuffle of words and araucarias (Extended abstract), Proceedings of MCU-2004 (International Conference on Machines, Computing and Universality, St Petersburg, September 2004), Lecture Notes in Computer Science, 3354, 316-327, Springer Verlag 2005.
• [17] Spehner J.-C., Le calcul rapide des mélanges de deux mots, Theoretical Computer Science, 47, 1986, 181-203.
• [18] Zielonka W., Notes on finite asynchronous automata and trace languages, RAIRO Inf. Theor., 21, 1987, 99-135.