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.
@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},
volume = {41},
year = {2007},
pages = {285-306},
doi = {10.1051/ita:2007020},
mrnumber = {2354359},
zbl = {pre05211861},
language = {en},
url = {http://dml.mathdoc.fr/item/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) pp. 285-306. doi : 10.1051/ita:2007020. http://gdmltest.u-ga.fr/item/ITA_2007__41_3_285_0/
[1] and, A complete invariant for the topology of one-dimensional substitution tiling spaces. Ergodic Theory Dynam. Systems 21 (2001) 1333-1358. | Zbl 0986.37015
[2] , and, Asymptotic orbits of primitive substitutions. Theoret. Comput. Sci. 301 (2003) 439-450. | Zbl 1022.68107
[3] and, Exponential subdynamics. Trans. Amer. Math. Soc. 349 (1997) 55-102. | Zbl 0863.54034
[4] and, Java applet, www.math.ku.dk/ẽilers/papers/cei (2002).
[5] and, Augmenting dimension group invariants for substitution dynamics. Ergodic Theory Dynam. Systems 24 (2004) 1015-1039. | Zbl 1060.37014
[6] and, Matsumoto K-groups associated to certain shift spaces. Doc. Math. 9 (2004) 639-671. | Zbl 1062.37004
[7] and, Ordered K-groups associated to substitutional dynamics. J. Funct. Anal. 238 (2006) 99-117. | Zbl 1105.46046
[8] ,, and, Substitutional dynamical systems, Bratteli diagrams and dimension groups. Ergodic Theory Dynam. Systems 19 (1999) 953-993. | Zbl 1044.46543
[9] , Substitutions in dynamics, arithmetics and combinatorics. Lect. Notes Math. 1794 Springer-Verlag, Heidelberg (2002). | MR 1970385
[10] and, Directed graphs and substitutions. Theory Comput. Syst. 34 (2001) 545-564. | Zbl 0993.68075
[11] , Symbolic dynamics; One-sided, two-sided and countable state Markov shifts. Springer-Verlag, Berlin (1998). | MR 1484730 | Zbl 0892.58020
[12] and, An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge (1995). | MR 1369092 | Zbl 1106.37301
[13] , Bowen-Franks groups as an invariant for flow equivalence of subshifts. Ergodic Theory Dynam. Systems 21 (2001) 1831-1842. | Zbl 1001.37009
[14] , Puissances de mots et reconnaissabilité des points fixes d'une substitution. Theoret. Comput. Sci. 99 (1992) 327-334. | Zbl 0763.68049
[15] , Decidability of periodicity for infinite words. RAIRO-Theor. Inf. Appl. 20 (1986) 43-46. | Numdam | Zbl 0617.68063
[16] and, A topological invariant of flows on -dimensional spaces. Topology 14 (1975) 297-299. | Zbl 0314.54045
[17] , Substitution dynamical systems-spectral analysis. Springer-Verlag, Berlin (1987). | MR 924156 | Zbl 0642.28013
[18] and, The mathematical theory of L systems. Academic Press Inc. Harcourt Brace Jovanovich Publishers, New York (1980). | MR 561711 | Zbl 0508.68031
[19] , Unzerlegbare, nicht negative Matrizen. Math. Z. 52 (1950) 642-648. | Zbl 0035.29101