Narzędzia help

Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
first last
cannonical link button


Fundamenta Informaticae

Tytuł artykułu

Araucaria Trees: Construction and Grafting Theorems

Autorzy Schmitt, D.  Spehner, J.-C. 
Treść / Zawartość
Warianty tytułu
Języki publikacji EN
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.
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,
[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.
Kolekcja BazTech
Identyfikator YADDA bwmeta1.element.baztech-6d2bf15a-98fe-4f88-baee-f7492abc4669