Tree algebra of sofic tree languages
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 4, pp. 431-451.

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 which is finer than the classical syntactic tree algebra based on contexts. This allows us to capture the notion of constant tree which is essential in the framework of tree-shift languages.

DOI : 10.1051/ita/2014018
Classification : 68501, 37B10
Mots-clés : symbolic dynamics, tree-shift, tree automata, tree algebra 
@article{ITA_2014__48_4_431_0,
     author = {Aubrun, Nathalie and B\'eal, Marie-Pierre},
     title = {Tree algebra of sofic tree languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {431--451},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {4},
     year = {2014},
     doi = {10.1051/ita/2014018},
     mrnumber = {3302496},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2014018/}
}
TY  - JOUR
AU  - Aubrun, Nathalie
AU  - Béal, Marie-Pierre
TI  - Tree algebra of sofic tree languages
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2014
SP  - 431
EP  - 451
VL  - 48
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2014018/
DO  - 10.1051/ita/2014018
LA  - en
ID  - ITA_2014__48_4_431_0
ER  - 
%0 Journal Article
%A Aubrun, Nathalie
%A Béal, Marie-Pierre
%T Tree algebra of sofic tree languages
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2014
%P 431-451
%V 48
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2014018/
%R 10.1051/ita/2014018
%G en
%F ITA_2014__48_4_431_0
Aubrun, Nathalie; Béal, Marie-Pierre. Tree algebra of sofic tree languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 4, pp. 431-451. doi : 10.1051/ita/2014018. http://www.numdam.org/articles/10.1051/ita/2014018/

[1] N. Aubrun and M.-P. Béal, Decidability of conjugacy of tree-shifts of finite type. In ICALP '09: Proc. of the 36th International Colloquium on Automata, Languages and Programming. Springer-Verlag Berlin, Heidelberg (2009) 132-143. | MR | Zbl

[2] N. Aubrun and M.-P. Béal, Sofic and almost of finite type tree-shifts. In 5th International Computer Science Symposium in Russia, (CSR'10), edited by E. Mayr and F. Ablayev, number 6072 in Lect. Notes Comput. Sci. Springer-Verlag (2010) 12-24. | MR | Zbl

[3] N. Aubrun and M.-P. Béal, Tree-shifts of finite type. Theoret. Comput. Sci. 459 (2012) 16-25. | MR | Zbl

[4] N. Aubrun and M.-P. Béal, Sofic tree-shifts. Theory Comput. Syst. 53 (2013) 621-644. | MR | Zbl

[5] M.-P. Béal, F. Fiorenzi and D. Perrin, A hierarchy of shift equivalent sofic shifts. Theoret. Comput. Sci. 345 (2005) 190-205. | MR | Zbl

[6] M. Bojanczyk, Algebra for Trees. In Handbook of Automata Theory. To appear in EMS Publishing.

[7] M. Bojanczyk, Effective characterizations of tree logics. Tutorial at PODS 2008 (2008).

[8] M. Bojanczyk, L. Segoufin and H. Straubing, Piecewise testable tree languages. In LICS (2008) 442-451. | MR | Zbl

[9] M. Boyle, B. Kitchens and B. Marcus, A note on minimal covers for sofic systems. Proc. Amer. Math. Soc. 95 (1985) 403-411. | MR | Zbl

[10] T. Ceccherini-Silberstein, M. Coornaert, F. Fiorenzi and Z. Sunic, Cellular automata on regular rooted trees. In CIAA 2012 (2012) 101-112. | MR | Zbl

[11] H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi, Tree automata techniques and applications. Available on: http://www.grappa.univ-lille3.fr/tata, release October, 12th (2007).

[12] A. De Luca and A. Restivo, A characterization of strictly locally testable languages and its applications to subsemigroups of a free semigroup. Inform. Control 44 (1980) 300-319. | MR | Zbl

[13] G. Fici and F. Fiorenzi, Topological properties of cellular automata on trees. In DCM (2012) 255-266.

[14] U. Heuter, Definite tree languages. Bulletin of the EATCS 35 (1988) 137-142. | Zbl

[15] U. Heuter, Generalized definite tree languages. In Mathematical Foundations of Computer Science 1989 (Pora¸bka-Kozubnik, 1989), vol. 379 of Lect. Notes Comput. Sci. Springer, Berlin (1989) 270-280. | MR | Zbl

[16] E. Jeandel and G. Theyssier, Subshifts, languages and logic. In Developments in Language Theory, 13th International Conference, DLT 2009, Stuttgart, Germany, June 30 - July 3, 2009. Proceedings, vol. 5583 of Lect. Notes Comput. Sci. Springer (2009). | MR | Zbl

[17] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge (1995). | MR | Zbl

[18] M. Nivat and A. Podelski, Definite tree languages. Bulletin of the EATCS 38 (1989) 186-190. | Zbl

[19] T. Place and L. Segoufin, A decidable characterization of locally testable tree languages. In ICALP (2), Lect. Notes Comput. Sci. Springer (2009) 285-296. | MR | Zbl

[20] S. Salehi, A completeness property of wilke's tree algebras. In MFCS, vol. 2747 of Lect. Notes Comput. Sci. Springer (2003) 662-670. | MR | Zbl

[21] J. Verdú-Mas, R. Carrasco and J. Calera-Rubio, Parsing with probabilistic strictly locally testable tree languages. IEEE Trans. Pattern Anal. Mach. Intell. 27 (2005) 1040-1050.

[22] T. Wilke, An algebraic characterization of frontier testable tree languages. Theoret. Comput. Sci. 154 (1996) 85-106. | MR | Zbl

Cité par Sources :