Skip to Main content Skip to Navigation
Conference papers

Sofic and Almost of Finite Type Tree-Shifts

Abstract : We introduce the notion of sofic tree-shifts which corresponds to symbolic dynamical systems of infinite trees accepted by finite tree automata. We show that, contrary to shifts of infinite sequences, there is no unique minimal deterministic irreducible tree automaton accepting an irreducible sofic tree-shift, but that there is a unique synchronized one, called the Shannon cover of the tree-shift. We define the notion of almost finite type tree-shift which is a meaningful intermediate dynamical class in between irreducible finite type tree-shifts and irreducible sofic tree-shifts. We characterize the Shannon cover of an almost finite type tree-shift and we design an algorithm to check whether a sofic tree-shift is almost of finite type.
Document type :
Conference papers
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620400
Contributor : Marie-Pierre Béal <>
Submitted on : Friday, September 30, 2011 - 3:43:12 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Saturday, December 31, 2011 - 2:21:43 AM

File

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620400, version 1

Citation

Nathalie Aubrun, Marie-Pierre Béal. Sofic and Almost of Finite Type Tree-Shifts. 5th International Computer Science Symposium in Russia (CSR'10), 2010, Russia. pp.12-24. ⟨hal-00620400⟩

Share

Metrics

Record views

241

Files downloads

271