On the syntactic complexity of tree series
Bozapalidis, Symeon ; Kalampakas, Antonios
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010), p. 257-279 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

We display a complexity notion based on the syntax of a tree series which yields two distinct hierarchies, one within the class of recognizable tree series and another one in the class of non-recognizable tree series.

Publié le : 2010-01-01
DOI : https://doi.org/10.1051/ita/2010014
Classification:  68Q01,  68Q15 
@article{ITA_2010__44_2_257_0,
     author = {Bozapalidis, Symeon and Kalampakas, Antonios},
     title = {On the syntactic complexity of tree series},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {44},
     year = {2010},
     pages = {257-279},
     doi = {10.1051/ita/2010014},
     mrnumber = {2674543},
     zbl = {pre05717749},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2010__44_2_257_0}
}

Bozapalidis, Symeon; Kalampakas, Antonios. On the syntactic complexity of tree series. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) pp. 257-279. doi : 10.1051/ita/2010014. http://gdmltest.u-ga.fr/item/ITA_2010__44_2_257_0/

[1] J. Berstel and C. Reutenauer, Recognizable formal power series on trees. Theoret. Comput. Sci. 18 (1982) 115-148. | Zbl 0485.68077

[2] S. Bozapalidis, Effective construction of the syntactic algebra of a recognizable series on trees. Acta Informatica 28 (1991) 351-363. | Zbl 0697.68074

[3] S. Bozapalidis and A. Alexandrakis, Représentations Matricielles des Séries d'Arbres Reconnaissables. Theor. Inf. Appl. 23 (1989) 449-459. | Numdam | Zbl 0689.68099

[4] S. Bozapalidis and O.L. Bozapalidou, The rank of a formal tree power series. Theoret. Comput. Sci. 27 (1983) 211-215. | Zbl 0537.68053

[5] S. Bozapalidis and A. Kalampakas, Recognizability of graph and pattern languages. Acta Informatica 42 (2006) 553-581. | Zbl 1089.68052

[6] S. Bozapalidis and A. Kalampakas, On the Complexity of the Syntax of Tree Languages, Proceedings of the 3rd International Conference of Algebraic Informatics, CAI09. Lect. Notes Comput. Sci. 5725 (2009) 189-203. | Zbl pre05625947

[7] F. Gécseg and M. Steinby, Tree Automata. Akademiai Kiado, Budapest (1984). | Zbl 0537.68056

[8] A. Kalampakas, The Syntactic Complexity of Eulerian Graphs, Proceedings of the 2nd International Conference of Algebraic Informatics, CAI07. Lect. Notes Comput. Sci. 4728 (2007) 208-217. | Zbl 1148.68401