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.

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.

DOI : https://doi.org/10.1051/ita:2007020
Classification : 37B10,  68R15
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://archive.numdam.org/articles/10.1051/ita:2007020/}
}
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://archive.numdam.org/articles/10.1051/ita:2007020/

[1] M. Barge and B. Diamond, A complete invariant for the topology of one-dimensional substitution tiling spaces. Ergodic Theory Dynam. Systems 21 (2001) 1333-1358. | Zbl 0986.37015

[2] M. Barge, B. Diamond and C. Holton, Asymptotic orbits of primitive substitutions. Theoret. Comput. Sci. 301 (2003) 439-450. | Zbl 1022.68107

[3] M. Boyle and D. Lind, Exponential subdynamics. Trans. Amer. Math. Soc. 349 (1997) 55-102. | Zbl 0863.54034

[4] T.M. Carlsen and S. Eilers, Java applet, www.math.ku.dk/ẽilers/papers/cei (2002).

[5] T.M. Carlsen and S. Eilers, Augmenting dimension group invariants for substitution dynamics. Ergodic Theory Dynam. Systems 24 (2004) 1015-1039. | Zbl 1060.37014

[6] T.M. Carlsen and S. Eilers, Matsumoto K-groups associated to certain shift spaces. Doc. Math. 9 (2004) 639-671. | Zbl 1062.37004

[7] T.M. Carlsen and S. Eilers, Ordered K-groups associated to substitutional dynamics. J. Funct. Anal. 238 (2006) 99-117. | Zbl 1105.46046

[8] F. Durand, B. Host, and C. Skau, Substitutional dynamical systems, Bratteli diagrams and dimension groups. Ergodic Theory Dynam. Systems 19 (1999) 953-993. | Zbl 1044.46543

[9] N.P. Fogg, Substitutions in dynamics, arithmetics and combinatorics. Lect. Notes Math. 1794 Springer-Verlag, Heidelberg (2002). | MR 1970385

[10] C. Holton and L.Q. Zamboni, Directed graphs and substitutions. Theory Comput. Syst. 34 (2001) 545-564. | Zbl 0993.68075

[11] B.P. Kitchens, Symbolic dynamics; One-sided, two-sided and countable state Markov shifts. Springer-Verlag, Berlin (1998). | MR 1484730 | Zbl 0892.58020

[12] D. Lind and B. Marcus, An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge (1995). | MR 1369092 | Zbl 1106.37301

[13] K. Matsumoto, Bowen-Franks groups as an invariant for flow equivalence of subshifts. Ergodic Theory Dynam. Systems 21 (2001) 1831-1842. | Zbl 1001.37009

[14] B. Mossé, Puissances de mots et reconnaissabilité des points fixes d'une substitution. Theoret. Comput. Sci. 99 (1992) 327-334. | Zbl 0763.68049

[15] J.-J. Pansiot, Decidability of periodicity for infinite words. RAIRO-Theor. Inf. Appl. 20 (1986) 43-46. | Numdam | Zbl 0617.68063

[16] B. Parry and D. Sullivan, A topological invariant of flows on 1-dimensional spaces. Topology 14 (1975) 297-299. | Zbl 0314.54045

[17] M. Queffélec, Substitution dynamical systems-spectral analysis. Springer-Verlag, Berlin (1987). | MR 924156 | Zbl 0642.28013

[18] G. Rozenberg and A. Salomaa, The mathematical theory of L systems. Academic Press Inc. Harcourt Brace Jovanovich Publishers, New York (1980). | MR 561711 | Zbl 0508.68031

[19] H. Wielandt, Unzerlegbare, nicht negative Matrizen. Math. Z. 52 (1950) 642-648. | Zbl 0035.29101