Sofic Tree-Shifts
- PDF / 880,569 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 31 Downloads / 150 Views
Sofic Tree-Shifts Nathalie Aubrun · Marie-Pierre Béal
Published online: 6 March 2013 © Springer Science+Business Media New York 2013
Abstract We introduce the notion of sofic tree-shifts which corresponds to symbolic dynamical systems of infinite ranked trees accepted by finite tree automata. We show that, contrary to shifts of infinite sequences, there is no unique reduced deterministic irreducible tree automaton accepting an irreducible sofic tree-shift, but that there is a unique synchronized one, called the Fischer automaton of the tree-shift. We define the notion of almost of finite type tree-shift which are sofic tree-shifts accepted by a tree automaton which is both deterministic and co-deterministic with a finite delay. It is a meaningful intermediate dynamical class in between irreducible finite type treeshifts and irreducible sofic tree-shifts. We characterize the Fischer automaton of an almost of finite type tree-shift and we design an algorithm to check whether a sofic tree-shift is almost of finite type. We prove that the Fischer automaton is a topological conjugacy invariant of the underlying irreducible sofic tree-shift. Keywords Symbolic dynamics · Tree automata · Tree-shift 1 Introduction In [1] we introduced the notion of tree-shifts of finite type defined as sets of infinite ranked trees avoiding a finite number of forbidden patterns. Infinite trees have This work is supported by the French National Agency (ANR) through “Programme d’Investissements d’Avenir” (Project ACRONYME n◦ ANR-10-LABX-58) and through the ANR SubTile. N. Aubrun LIP, UMR 5668, ENS de Lyon - CNRS - UCBL - INRIA, 46 allée d’Italie, 69364 Lyon Cedex, France e-mail: [email protected] M.-P. Béal () Laboratoire d’informatique Gaspard-Monge, UMR 8049, CNRS, Université Paris-Est, 77 454 Marne-la-Vallée Cedex 2, France e-mail: [email protected]
622
Theory Comput Syst (2013) 53:621–644
a natural structure of one-sided symbolic dynamical systems equipped with several shift transformations. The ith shift transformation applied to a tree gives the subtree rooted at the child number i of the tree. Sets of finite patterns of tree-shifts of finite type are strictly locally testable tree languages [29] (also called k-testable tree languages, or k-grams in the case of sequences). For these languages, the effect of events that occured beyond a certain depth window are ignored when processing a tree. Probabilistic k-testable models are used for pattern classification and stochastic learning [29]. Tree-shifts are also highly interesting to study as they constitute an intermediate class in between one-sided shifts of infinite sequences and multidimensional shifts. The conjugacy of multidimensional shifts of finite type, also called textile systems or tiling systems (see for instance [11, 15, 19, 22]), is undecidable. The decidability of the conjugacy of finite type shifts of bi-infinite sequences is unknown. However, the conjugacy of finite shifts of one-sided infinite sequences was shown to be decidable by Williams ([30], see also [
Data Loading...
