We present an algorithm which for any aperiodic and primitive substitution outputs a finite representation of each special word in the shift space associated to that substitution, and determines when such representations are equivalent under orbit and shift tail equivalence. The algorithm has been implemented and applied in the study of certain new invariants for flow equivalence of substitutional dynamical systems.
Mots clés : sustitution, shift spaces, special elements, orbit equivalence, shift tail equivalence
@article{ITA_2007__41_3_285_0, author = {Carlsen, Toke M. and Eilers, S{\o}ren}, title = {A graph approach to computing nondeterminacy in substitutional dynamical systems}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {285--306}, publisher = {EDP-Sciences}, volume = {41}, number = {3}, year = {2007}, doi = {10.1051/ita:2007020}, mrnumber = {2354359}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ita:2007020/} }
TY - JOUR AU - Carlsen, Toke M. AU - Eilers, Søren TI - A graph approach to computing nondeterminacy in substitutional dynamical systems JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2007 SP - 285 EP - 306 VL - 41 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2007020/ DO - 10.1051/ita:2007020 LA - en ID - ITA_2007__41_3_285_0 ER -
%0 Journal Article %A Carlsen, Toke M. %A Eilers, Søren %T A graph approach to computing nondeterminacy in substitutional dynamical systems %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2007 %P 285-306 %V 41 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2007020/ %R 10.1051/ita:2007020 %G en %F ITA_2007__41_3_285_0
Carlsen, Toke M.; Eilers, Søren. A graph approach to computing nondeterminacy in substitutional dynamical systems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 3, pp. 285-306. doi : 10.1051/ita:2007020. http://www.numdam.org/articles/10.1051/ita:2007020/
[1] A complete invariant for the topology of one-dimensional substitution tiling spaces. Ergodic Theory Dynam. Systems 21 (2001) 1333-1358. | Zbl
and ,[2] Asymptotic orbits of primitive substitutions. Theoret. Comput. Sci. 301 (2003) 439-450. | Zbl
, and ,[3] Exponential subdynamics. Trans. Amer. Math. Soc. 349 (1997) 55-102. | Zbl
and ,[4] Java applet, www.math.ku.dk/ẽilers/papers/cei (2002).
and ,[5] Augmenting dimension group invariants for substitution dynamics. Ergodic Theory Dynam. Systems 24 (2004) 1015-1039. | Zbl
and ,[6] Matsumoto K-groups associated to certain shift spaces. Doc. Math. 9 (2004) 639-671. | Zbl
and ,[7] Ordered K-groups associated to substitutional dynamics. J. Funct. Anal. 238 (2006) 99-117. | Zbl
and ,[8] Substitutional dynamical systems, Bratteli diagrams and dimension groups. Ergodic Theory Dynam. Systems 19 (1999) 953-993. | Zbl
, , and ,[9] Substitutions in dynamics, arithmetics and combinatorics. Lect. Notes Math. 1794 Springer-Verlag, Heidelberg (2002). | MR
,[10] Directed graphs and substitutions. Theory Comput. Syst. 34 (2001) 545-564. | Zbl
and ,[11] Symbolic dynamics; One-sided, two-sided and countable state Markov shifts. Springer-Verlag, Berlin (1998). | MR | Zbl
,[12] An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge (1995). | MR | Zbl
and ,[13] Bowen-Franks groups as an invariant for flow equivalence of subshifts. Ergodic Theory Dynam. Systems 21 (2001) 1831-1842. | Zbl
,[14] Puissances de mots et reconnaissabilité des points fixes d'une substitution. Theoret. Comput. Sci. 99 (1992) 327-334. | Zbl
,[15] Decidability of periodicity for infinite words. RAIRO-Theor. Inf. Appl. 20 (1986) 43-46. | Numdam | Zbl
,[16] A topological invariant of flows on -dimensional spaces. Topology 14 (1975) 297-299. | Zbl
and ,[17] Substitution dynamical systems-spectral analysis. Springer-Verlag, Berlin (1987). | MR | Zbl
,[18] The mathematical theory of L systems. Academic Press Inc. Harcourt Brace Jovanovich Publishers, New York (1980). | MR | Zbl
and ,[19] Unzerlegbare, nicht negative Matrizen. Math. Z. 52 (1950) 642-648. | Zbl
,Cité par Sources :