# Tree algebra of sofic tree languages

Nathalie Aubrun; Marie-Pierre Béal

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2014)

- Volume: 48, Issue: 4, page 431-451
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topAubrun, Nathalie, and Béal, Marie-Pierre. "Tree algebra of sofic tree languages." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 48.4 (2014): 431-451. <http://eudml.org/doc/273013>.

@article{Aubrun2014,

abstract = {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.},

author = {Aubrun, Nathalie, Béal, Marie-Pierre},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {symbolic dynamics; tree-shift; tree automata; tree algebra},

language = {eng},

number = {4},

pages = {431-451},

publisher = {EDP-Sciences},

title = {Tree algebra of sofic tree languages},

url = {http://eudml.org/doc/273013},

volume = {48},

year = {2014},

}

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

PB - EDP-Sciences

VL - 48

IS - 4

SP - 431

EP - 451

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

LA - eng

KW - symbolic dynamics; tree-shift; tree automata; tree algebra

UR - http://eudml.org/doc/273013

ER -

## References

top- [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. Zbl1248.68283MR2544841
- [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. Zbl1285.68078MR2972321
- [3] N. Aubrun and M.-P. Béal, Tree-shifts of finite type. Theoret. Comput. Sci.459 (2012) 16–25. Zbl1279.68128MR2974235
- [4] N. Aubrun and M.-P. Béal, Sofic tree-shifts. Theory Comput. Syst.53 (2013) 621–644. Zbl1293.68195MR3084356
- [5] M.-P. Béal, F. Fiorenzi and D. Perrin, A hierarchy of shift equivalent sofic shifts. Theoret. Comput. Sci.345 (2005) 190–205. Zbl1079.68048MR2171610
- [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. Zbl1261.03126MR2987919
- [9] M. Boyle, B. Kitchens and B. Marcus, A note on minimal covers for sofic systems. Proc. Amer. Math. Soc.95 (1985) 403–411. Zbl0606.28016MR806078
- [10] T. Ceccherini–Silberstein, M. Coornaert, F. Fiorenzi and Z. Sunic, Cellular automata on regular rooted trees. In CIAA2012 (2012) 101–112. Zbl1297.68175MR2993177
- [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. Control44 (1980) 300–319. Zbl0441.68087MR574489
- [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 EATCS35 (1988) 137–142. Zbl0676.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. Zbl0755.68087MR1036806
- [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). Zbl1247.03068MR2544709
- [17] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge (1995). Zbl1106.37301MR1369092
- [18] M. Nivat and A. Podelski, Definite tree languages. Bulletin of the EATCS38 (1989) 186–190. Zbl0677.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. Zbl1248.68313MR2544803
- [20] S. Salehi, A completeness property of wilke’s tree algebras. In MFCS, vol. 2747 of Lect. Notes Comput. Sci. Springer (2003) 662–670. Zbl1124.68389MR2081616
- [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. Zbl0871.68110MR1374381

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.