On the syntactic complexity of tree series
Symeon Bozapalidis; Antonios Kalampakas
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 44, Issue: 2, page 257-279
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topBozapalidis, Symeon, and Kalampakas, Antonios. "On the syntactic complexity of tree series." RAIRO - Theoretical Informatics and Applications 44.2 (2010): 257-279. <http://eudml.org/doc/250696>.
@article{Bozapalidis2010,
abstract = {
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.
},
author = {Bozapalidis, Symeon, Kalampakas, Antonios},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Tree series; syntactic complexity; recognizability; tree series},
language = {eng},
month = {5},
number = {2},
pages = {257-279},
publisher = {EDP Sciences},
title = {On the syntactic complexity of tree series},
url = {http://eudml.org/doc/250696},
volume = {44},
year = {2010},
}
TY - JOUR
AU - Bozapalidis, Symeon
AU - Kalampakas, Antonios
TI - On the syntactic complexity of tree series
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/5//
PB - EDP Sciences
VL - 44
IS - 2
SP - 257
EP - 279
AB -
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.
LA - eng
KW - Tree series; syntactic complexity; recognizability; tree series
UR - http://eudml.org/doc/250696
ER -
References
top- J. Berstel and C. Reutenauer, Recognizable formal power series on trees. Theoret. Comput. Sci.18 (1982) 115–148.
- S. Bozapalidis, Effective construction of the syntactic algebra of a recognizable series on trees. Acta Informatica28 (1991) 351–363.
- S. Bozapalidis and A. Alexandrakis, Représentations Matricielles des Séries d'Arbres Reconnaissables. Theor. Inf. Appl.23 (1989) 449–459.
- S. Bozapalidis and O.L. Bozapalidou, The rank of a formal tree power series. Theoret. Comput. Sci.27 (1983) 211–215.
- S. Bozapalidis and A. Kalampakas, Recognizability of graph and pattern languages. Acta Informatica42 (2006) 553–581.
- 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.
- F. Gécseg and M. Steinby, Tree Automata. Akademiai Kiado, Budapest (1984).
- 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.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.