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.
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita/2014018/
[1] 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
and ,[2] 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
and ,[3] Tree-shifts of finite type. Theoret. Comput. Sci. 459 (2012) 16-25. | MR | Zbl
and ,[4] Sofic tree-shifts. Theory Comput. Syst. 53 (2013) 621-644. | MR | Zbl
and ,[5] A hierarchy of shift equivalent sofic shifts. Theoret. Comput. Sci. 345 (2005) 190-205. | MR | Zbl
, and ,[6] Algebra for Trees. In Handbook of Automata Theory. To appear in EMS Publishing.
,[7] Effective characterizations of tree logics. Tutorial at PODS 2008 (2008).
,[8] Piecewise testable tree languages. In LICS (2008) 442-451. | MR | Zbl
, and ,[9] A note on minimal covers for sofic systems. Proc. Amer. Math. Soc. 95 (1985) 403-411. | MR | Zbl
, and ,[10] Cellular automata on regular rooted trees. In CIAA 2012 (2012) 101-112. | MR | Zbl
, , and ,[11] Tree automata techniques and applications. Available on: http://www.grappa.univ-lille3.fr/tata, release October, 12th (2007).
, , , , , , and ,[12] A characterization of strictly locally testable languages and its applications to subsemigroups of a free semigroup. Inform. Control 44 (1980) 300-319. | MR | Zbl
and ,[13] Topological properties of cellular automata on trees. In DCM (2012) 255-266.
and ,[14] Definite tree languages. Bulletin of the EATCS 35 (1988) 137-142. | Zbl
,[15] 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] 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
and ,[17] An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge (1995). | MR | Zbl
and ,[18] Definite tree languages. Bulletin of the EATCS 38 (1989) 186-190. | Zbl
and ,[19] A decidable characterization of locally testable tree languages. In ICALP (2), Lect. Notes Comput. Sci. Springer (2009) 285-296. | MR | Zbl
and ,[20] A completeness property of wilke's tree algebras. In MFCS, vol. 2747 of Lect. Notes Comput. Sci. Springer (2003) 662-670. | MR | Zbl
,[21] Parsing with probabilistic strictly locally testable tree languages. IEEE Trans. Pattern Anal. Mach. Intell. 27 (2005) 1040-1050.
, and ,[22] An algebraic characterization of frontier testable tree languages. Theoret. Comput. Sci. 154 (1996) 85-106. | MR | Zbl
,Cité par Sources :