Sofic tree-shifts (Q385506)

The authors [Lect. Notes Comput. Sci. 5555, 132--143 (2009; Zbl 1248.68283)] introduced a notion of tree-shifts of finite type as sets of infinite ranked trees avoiding a finite number of forbidden patterns. The structure of an infinite tree may be thought of as a symbolic dynamical system with several transformations, giving the subtree rooted at the various children of the tree. These structures, studied in language theory and in symbolic dynamics, are of interest because they are intermediate between one-sided shifts of infinite sequences and the considerably more complex multi-dimensional shifts. Here the focus is on sofic tree-shifts, namely those shifts of infinite trees accepted by finite bottom-up tree automata, with the aim of extending to this setting some results for sofic shifts of infinite sequences. Several results related to various tree-shifts of this sort are found, concerning both their dynamical properties and their language- and automata-theoretic properties.