A graph approach to computing nondeterminacy in substitutional dynamical systems

Toke M. Carlsen; Søren Eilers

RAIRO - Theoretical Informatics and Applications (2007)

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

Abstract

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

How to cite

top

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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.