Powiadomienia systemowe
- Sesja wygasła!
- Sesja wygasła!
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Wydawca
Czasopismo
Rocznik
Tom
Strony
417--445
Opis fizyczny
Bibliogr. 12 poz., rys.
Twórcy
autor
- Laboratoire LMIA, Equipe MAGE, Universit´e de Haute Alsace 4, rue des Fr`eres Lumi`ere, 68093 Mulhouse, France
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-6d2bf15a-98fe-4f88-baee-f7492abc4669