Skip to Main content Skip to Navigation
Journal articles

Tree-shifts of finite type

Abstract : A one-sided (resp. two-sided) shift of finite type of dimension one can be described as the set of infinite (resp. bi-infinite) sequences of consecutive edges in a finite-state automaton. While the conjugacy of shifts of finite type is decidable for one-sided shifts of finite type of dimension one, the result is unknown in the two-sided case. In this paper, we study the shifts of finite type defined by infinite ranked trees. Indeed, infinite ranked trees have a natural structure of symbolic dynamical systems. We prove a decomposition Theorem for these tree-shifts, i.e. we show that a conjugacy between two tree-shifts can be broken down into a finite sequence of elementary transformations called in-splittings and in-amalgamations. We prove that the conjugacy problem is decidable for tree-shifts of finite type. This result makes the class of tree-shifts closer to the class of one-sided shifts of sequences than to the class of two-sided ones. Our proof uses the notion of bottom-up tree automata.
Document type :
Journal articles
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00627800
Contributor : Marie-Pierre Béal <>
Submitted on : Thursday, September 29, 2011 - 3:56:41 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Friday, December 30, 2011 - 2:26:21 AM

File

HAL.pdf
Files produced by the author(s)

Identifiers

Citation

Nathalie Aubrun, Marie-Pierre Béal. Tree-shifts of finite type. Theoretical Computer Science, Elsevier, 2012, 459, pp.16-25. ⟨10.1016/j.tcs.2012.07.020⟩. ⟨hal-00627800⟩

Share

Metrics

Record views

259

Files downloads

232