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 : 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://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] 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

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

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

[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

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

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

[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

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

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

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

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

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

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

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

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

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

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

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

Cité par Sources :