Tree algebra of sofic tree languages
Aubrun, Nathalie ; Béal, Marie-Pierre
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014), p. 431-451 / Harvested from Numdam
Access to full text

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.

Publié le : 2014-01-01
DOI : https://doi.org/10.1051/ita/2014018
Classification:  68501,  37B10 
@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},
     volume = {48},
     year = {2014},
     pages = {431-451},
     doi = {10.1051/ita/2014018},
     mrnumber = {3302496},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 431-451. doi : 10.1051/ita/2014018. http://gdmltest.u-ga.fr/item/ITA_2014__48_4_431_0/

[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 2544841 | Zbl 1248.68283

[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 2972321 | Zbl 1285.68078

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

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

[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 2171610 | Zbl 1079.68048

[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 2987919 | Zbl 1261.03126

[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 806078 | Zbl 0606.28016

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

[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 574489 | Zbl 0441.68087

[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 0676.68027

[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 1036806 | Zbl 0755.68087

[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 2544709 | Zbl 1247.03068

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

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

[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 2544803 | Zbl 1248.68313

[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 2081616 | Zbl 1124.68389

[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 1374381 | Zbl 0871.68110