Araucaria Trees: Construction and Grafting Theorems

• Autorzy: Schmitt D. , Spehner J-C.
• Języki publikacji: EN

Abstrakty

EN

Araucarias have been introduced by Schott and Spehner as trees which appear in the minimal automaton of the shuffle of words. We give here a new definition of araucarias which is more constructive and we prove that our definition of araucarias is equivalent to the original one. From the new definition we derive an optimal algorithm for the construction of araucarias and a new method for calculating their size. Moreover we characterize araucarias by properties of their maximal paths, by associating a capacity to every edge. We then show that every araucaria can be obtained by grafting and merging smaller araucarias. We prove also that every directed tree can be embedded in an araucaria. Moreover we define a capacity for every vertex of an araucaria, which leads to different new enumeration formulas for araucarias.

Słowa kluczowe

EN

algorithms; trees; symmetric polynomials; combinatorics; shuffle of words

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 123, nr 4
• Strony: 417--445
• Opis fizyczny: Bibliogr. 12 poz., rys.

Twórcy

autor

Schmitt D.

• Laboratoire LMIA, Equipe MAGE, Universit´e de Haute Alsace 4, rue des Fr`eres Lumi`ere, 68093 Mulhouse, France

autor

Spehner J-C.

• Laboratoire LMIA, Equipe MAGE, Universit´e de Haute Alsace 4, rue des Fr`eres Lumi`ere, 68093 Mulhouse, France

Bibliografia

• [1] Berstel, J., Boasson, L.: Shuffle factorization is unique, Theoretical Computer Science, 273(1-2), 2002, 47–67.
• [2] Biegler, F., Daley, M., McQuillan, I.: On the shuffle automaton size for words, Journal of Automata, Languages and Combinatorics, 15(1/2), 2010, 53–70.
• [3] Gómez, A. C., Pin, J.-E.: On a conjecture of Schnoebelen, in: Proceedings of the 7th international conference on Developments in Language Theory, vol. 2710 of LNCS, Springer, 2003, 35–54.
• [4] Lothaire, M.: Combinatorics on words, Encyclopedia of Mathematics, Vol.17, Addison-Wesley, 1983.
• [5] Lothaire, M.: Algebraic combinatorics on words, Cambridge University Press, 2002.
• [6] Nivat, M., Ramkumar, G. D. S., Rangan, C. P., Saoudi, A., Sundaram, R.: Efficient parallel shuffle recognition, Parallel Processing Letters, 4, 1994, 455–463.
• [7] Schmitt, D., Spehner, J.-C.: Construction of araucaria trees, in: Proceedings of the Kyoto international Conference of Computational Geometry and Graph Theory, 2007, 128–129.
• [8] Schnoebelen, P.: Decomposable regular languages and the shuffle operator, EATCS Bulletin, 67, 1999, 283–289.
• [9] Schott, R., Spehner, J.-C.: On the minimal automaton of the shuffle of words and araucarias, in: Proceedings of the 4th international conference on Machines, Computations, and Universality 2004, vol. 3354 of LNCS, Springer, 2005, 316–327.
• [10] Schott, R., Spehner, J.-C.: Shuffle of words and araucaria trees, Fundamenta Informaticae, 74(4), 2006, 579–601.
• [11] Schott, R., Spehner, J.-C.: Erratum for ”Shuffle of words and araucaria trees”, Fundamenta Informaticae, 81(4), 2007, 485–490.
• [12] Spehner, J.-C.: Le calcul rapide des m´elanges de deux mots, Theoretical Computer Science, 47(2), 1986, 181–203.