Tree-shifts of finite typeReportar como inadecuado

Tree-shifts of finite type - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LIGM - Laboratoire d-Informatique Gaspard-Monge

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.

Autor: Nathalie Aubrun - Marie-Pierre Béal -



Documentos relacionados