Skip to Main content Skip to Navigation
Journal articles

Sofic Tree-Shifts

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 tree-shifts 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 shift.
Document type :
Journal articles
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00627797
Contributor : Marie-Pierre Béal <>
Submitted on : Monday, February 18, 2013 - 4:39:50 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Sunday, May 19, 2013 - 4:04:50 AM

File

TOCS2012.pdf
Publisher files allowed on an open archive

Identifiers

Citation

Nathalie Aubrun, Marie-Pierre Béal. Sofic Tree-Shifts. Theory of Computing Systems, Springer Verlag, 2013, 53 (4), pp.621-644. ⟨10.1007/s00224-013-9456-1⟩. ⟨hal-00627797v2⟩

Share

Metrics

Record views

353

Files downloads

323