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

Abstract

top
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.

How to cite

top

Bozapalidis, 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
  1. J. Berstel and C. Reutenauer, Recognizable formal power series on trees. Theoret. Comput. Sci.18 (1982) 115–148.  Zbl0485.68077
  2. S. Bozapalidis, Effective construction of the syntactic algebra of a recognizable series on trees. Acta Informatica28 (1991) 351–363.  Zbl0697.68074
  3. S. Bozapalidis and A. Alexandrakis, Représentations Matricielles des Séries d'Arbres Reconnaissables. Theor. Inf. Appl.23 (1989) 449–459.  
  4. S. Bozapalidis and O.L. Bozapalidou, The rank of a formal tree power series. Theoret. Comput. Sci.27 (1983) 211–215.  Zbl0537.68053
  5. S. Bozapalidis and A. Kalampakas, Recognizability of graph and pattern languages. Acta Informatica42 (2006) 553–581.  Zbl1089.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.  Zbl1256.68097
  7. F. Gécseg and M. Steinby, Tree Automata. Akademiai Kiado, Budapest (1984).  
  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.  Zbl1148.68401

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.