RAIRO - Theoretical Informatics and Applications

Table of Contents - April 2010 - Volume 44, Issue 02  

Research Article

On the syntactic complexity of tree series

Bozapalidis, Symeona1 and Kalampakas, Antoniosa2a3

a1 Aristotle University of Thessaloniki, Department of Mathematics, 54124 Thessaloniki, Greece; bozapali@math.auth.gr

a2 Democritus University of Thrace, Department of Production Engineering and Management, 67100 Xanti, Greece; akalamp@math.auth.gr

a3 Technical Institute of Kavala, Department of Exact Sciences, 65404 Kavala, Greece.

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.

(Received March 17 2009)

(Accepted December 16 2009)

(Online publication January 26 2010)

Key Words:

  • Tree series;
  • syntactic complexity;
  • recognizability

Mathematics Subject Classification:

  • 68Q01;
  • 68Q15