Tree algebra of sofic tree languages
Nathalie Aubrun, Marie-Pierre Béal (2014)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We consider the languages of finite trees called tree-shift languages which are factorial extensible tree languages. These languages are sets of factors of subshifts of infinite trees. We give effective syntactic characterizations of two classes of regular tree-shift languages: the finite type tree languages and the tree languages which are almost of finite type. Each class corresponds to a class of subshifts of trees which is invariant by conjugacy. For this goal, we define a tree algebra...