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

Abstract

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

How to cite

top

Aubrun, 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. [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. [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. [3] N. Aubrun and M.-P. Béal, Tree-shifts of finite type. Theoret. Comput. Sci.459 (2012) 16–25. Zbl1279.68128MR2974235
  4. [4] N. Aubrun and M.-P. Béal, Sofic tree-shifts. Theory Comput. Syst.53 (2013) 621–644. Zbl1293.68195MR3084356
  5. [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. [6] M. Bojanczyk, Algebra for Trees. In Handbook of Automata Theory. To appear in EMS Publishing. 
  7. [7] M. Bojanczyk, Effective characterizations of tree logics. Tutorial at PODS 2008 (2008). 
  8. [8] M. Bojanczyk, L. Segoufin and H. Straubing, Piecewise testable tree languages. In LICS (2008) 442–451. Zbl1261.03126MR2987919
  9. [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. [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. [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. [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. [13] G. Fici and F. Fiorenzi, Topological properties of cellular automata on trees. In DCM (2012) 255–266. 
  14. [14] U. Heuter, Definite tree languages. Bulletin of the EATCS35 (1988) 137–142. Zbl0676.68027
  15. [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. [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. [17] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge (1995). Zbl1106.37301MR1369092
  18. [18] M. Nivat and A. Podelski, Definite tree languages. Bulletin of the EATCS38 (1989) 186–190. Zbl0677.68066
  19. [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. [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. [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. [22] T. Wilke, An algebraic characterization of frontier testable tree languages. Theoret. Comput. Sci.154 (1996) 85–106. Zbl0871.68110MR1374381

NotesEmbed ?

top

You must be logged in to post comments.