# A graph approach to computing nondeterminacy in substitutional dynamical systems

RAIRO - Theoretical Informatics and Applications (2007)

- Volume: 41, Issue: 3, page 285-306
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topCarlsen, Toke M., and Eilers, Søren. "A graph approach to computing nondeterminacy in substitutional dynamical systems ." RAIRO - Theoretical Informatics and Applications 41.3 (2007): 285-306. <http://eudml.org/doc/250063>.

@article{Carlsen2007,

abstract = {
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.
},

author = {Carlsen, Toke M., Eilers, Søren},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Sustitution; shift spaces; special elements; orbit equivalence; shift tail equivalence; sustitution},

language = {eng},

month = {9},

number = {3},

pages = {285-306},

publisher = {EDP Sciences},

title = {A graph approach to computing nondeterminacy in substitutional dynamical systems },

url = {http://eudml.org/doc/250063},

volume = {41},

year = {2007},

}

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

DA - 2007/9//

PB - EDP Sciences

VL - 41

IS - 3

SP - 285

EP - 306

AB -
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.

LA - eng

KW - Sustitution; shift spaces; special elements; orbit equivalence; shift tail equivalence; sustitution

UR - http://eudml.org/doc/250063

ER -

## References

top- M. Barge and B. Diamond, A complete invariant for the topology of one-dimensional substitution tiling spaces. Ergodic Theory Dynam. Systems21 (2001) 1333–1358.
- M. Barge, B. Diamond and C. Holton, Asymptotic orbits of primitive substitutions. Theoret. Comput. Sci.301 (2003) 439–450.
- M. Boyle and D. Lind, Exponential subdynamics. Trans. Amer. Math. Soc.349 (1997) 55–102.
- T.M. Carlsen and S. Eilers, Java applet, www.math.ku.dk/ẽilers/papers/cei (2002).
- T.M. Carlsen and S. Eilers, Augmenting dimension group invariants for substitution dynamics. Ergodic Theory Dynam. Systems24 (2004) 1015–1039.
- T.M. Carlsen and S. Eilers, Matsumoto K-groups associated to certain shift spaces. Doc. Math.9 (2004) 639–671.
- T.M. Carlsen and S. Eilers, Ordered K-groups associated to substitutional dynamics. J. Funct. Anal.238 (2006) 99–117.
- F. Durand, B. Host, and C. Skau, Substitutional dynamical systems, Bratteli diagrams and dimension groups. Ergodic Theory Dynam. Systems19 (1999) 953–993.
- N.P. Fogg, Substitutions in dynamics, arithmetics and combinatorics. Lect. Notes Math.1794 Springer-Verlag, Heidelberg (2002).
- C. Holton and L.Q. Zamboni, Directed graphs and substitutions. Theory Comput. Syst.34 (2001) 545–564.
- B.P. Kitchens, Symbolic dynamics; One-sided, two-sided and countable state Markov shifts. Springer-Verlag, Berlin (1998).
- D. Lind and B. Marcus, An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge (1995).
- K. Matsumoto, Bowen-Franks groups as an invariant for flow equivalence of subshifts. Ergodic Theory Dynam. Systems21 (2001) 1831–1842.
- B. Mossé, Puissances de mots et reconnaissabilité des points fixes d'une substitution. Theoret. Comput. Sci.99 (1992) 327–334.
- J.-J. Pansiot, Decidability of periodicity for infinite words. RAIRO-Theor. Inf. Appl.20 (1986) 43–46.
- B. Parry and D. Sullivan, A topological invariant of flows on 1-dimensional spaces. Topology14 (1975) 297–299.
- M. Queffélec, Substitution dynamical systems—spectral analysis. Springer-Verlag, Berlin (1987).
- G. Rozenberg and A. Salomaa, The mathematical theory of L systems. Academic Press Inc. Harcourt Brace Jovanovich Publishers, New York (1980).
- H. Wielandt, Unzerlegbare, nicht negative Matrizen. Math. Z.52 (1950) 642–648.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.