-
Previous Article
Recurrence for measurable semigroup actions
- DCDS Home
- This Issue
-
Next Article
Classification of nonnegative solutions to an equation involving the Laplacian of arbitrary order
The relationship between word complexity and computational complexity in subshifts
| 1. | Department of Mathematics, University of Denver, 2390 S. York St., Denver, CO 80208 |
| 2. | Normandie Univ, UNICAEN, ENSICAEN, CNRS, GREYC, 14000 CAEN, France, LACL – Université Paris-Est Créteil, 61 avenue du Général de Gaulle, 94010 Créteil Cedex, France |
We prove several results about the relationship between the word complexity function of a subshift and the set of Turing degrees of points of the subshift, which we call the Turing spectrum. Among other results, we show that a Turing spectrum can be realized via a subshift of linear complexity if and only if it consists of the union of a finite set and a finite number of cones, that a Turing spectrum can be realized via a subshift of exponential complexity (i.e. positive entropy) if and only if it contains a cone, and that every Turing spectrum which either contains degree $ {{\mathbf{0}}}$ or is a union of cones is realizable by subshifts with a wide range of 'intermediate' complexity growth rates between linear and exponential.
References:
| [1] |
J. Cassaigne, Special factors of sequences with linear subword complexity, in Developments in Language Theory II, At the Crossroads of Mathematics, Computer Science and Biology, Magdeburg, Germany, 17-21 July 1995, 1995, 25–34. |
| [2] |
S. B. Cooper, Computability Theory, Chapman & Hall/CRC Mathematics Series, Chapman & Hall/CRC, 2004. |
| [3] |
E. Coven, A. Johnson, N. Jonoska and K. Madden,
The symbolic dynamics of multidimensional tiling systems, Ergodic Theory and Dynamical Systems, 23 (2003), 447-460.
doi: 10.1017/S014338570200113X. |
| [4] |
M. Hochman and T. Meyerovitch,
A characterization of the entropies of multidimensional shifts of finite type, Annals of Mathematics, 171 (2010), 2011-2038.
doi: 10.4007/annals.2010.171.2011. |
| [5] |
M. Hochman and P. Vanier, Turing degree spectra of minimal subshifts, Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8-12, 2017,154–161.
doi: 10.1007/978-3-319-58747-9_15. |
| [6] |
E. Jeandel and P. Vanier,
Turing degrees of multidimensional SFTs, Theoretical Computer Science, 505 (2013), 81-92.
doi: 10.1016/j.tcs.2012.08.027. |
| [7] |
T. Kent and A. Lewis,
On the degree spectrum of a $\Pi^0_1$ class, Transactions of the American Mathematical Society, 362 (2010), 5283-5319.
doi: 10.1090/S0002-9947-10-05037-3. |
| [8] |
M. Lothaire, Algebraic Combinatorics on Words, 2002.
doi: 10.1017/CBO9780511566097. |
| [9] |
E. McCarthy,
Cototal enumeration degrees and their applications to effective mathematics, Proceedings of the American Mathematical Society, 146 (2018), 3541-3552.
doi: 10.1090/proc/13783. |
| [10] |
J. S. Miller,
Two notes on subshifts, Proceedings of the American Mathematical Society, 140 (2012), 1617-1622.
doi: 10.1090/S0002-9939-2011-11000-1. |
| [11] |
H. Rogers, Theory of Recursive Functions and Effective Computability, MIT Press Cambridge, MA, USA, 1987. |
| [12] |
P. Walters, An Introduction to Ergodic Theory, Graduate Texts in Mathematics, 79, Springer, 1982. |
show all references
References:
| [1] |
J. Cassaigne, Special factors of sequences with linear subword complexity, in Developments in Language Theory II, At the Crossroads of Mathematics, Computer Science and Biology, Magdeburg, Germany, 17-21 July 1995, 1995, 25–34. |
| [2] |
S. B. Cooper, Computability Theory, Chapman & Hall/CRC Mathematics Series, Chapman & Hall/CRC, 2004. |
| [3] |
E. Coven, A. Johnson, N. Jonoska and K. Madden,
The symbolic dynamics of multidimensional tiling systems, Ergodic Theory and Dynamical Systems, 23 (2003), 447-460.
doi: 10.1017/S014338570200113X. |
| [4] |
M. Hochman and T. Meyerovitch,
A characterization of the entropies of multidimensional shifts of finite type, Annals of Mathematics, 171 (2010), 2011-2038.
doi: 10.4007/annals.2010.171.2011. |
| [5] |
M. Hochman and P. Vanier, Turing degree spectra of minimal subshifts, Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8-12, 2017,154–161.
doi: 10.1007/978-3-319-58747-9_15. |
| [6] |
E. Jeandel and P. Vanier,
Turing degrees of multidimensional SFTs, Theoretical Computer Science, 505 (2013), 81-92.
doi: 10.1016/j.tcs.2012.08.027. |
| [7] |
T. Kent and A. Lewis,
On the degree spectrum of a $\Pi^0_1$ class, Transactions of the American Mathematical Society, 362 (2010), 5283-5319.
doi: 10.1090/S0002-9947-10-05037-3. |
| [8] |
M. Lothaire, Algebraic Combinatorics on Words, 2002.
doi: 10.1017/CBO9780511566097. |
| [9] |
E. McCarthy,
Cototal enumeration degrees and their applications to effective mathematics, Proceedings of the American Mathematical Society, 146 (2018), 3541-3552.
doi: 10.1090/proc/13783. |
| [10] |
J. S. Miller,
Two notes on subshifts, Proceedings of the American Mathematical Society, 140 (2012), 1617-1622.
doi: 10.1090/S0002-9939-2011-11000-1. |
| [11] |
H. Rogers, Theory of Recursive Functions and Effective Computability, MIT Press Cambridge, MA, USA, 1987. |
| [12] |
P. Walters, An Introduction to Ergodic Theory, Graduate Texts in Mathematics, 79, Springer, 1982. |
| [1] |
Frédéric Naud. Birkhoff cones, symbolic dynamics and spectrum of transfer operators. Discrete and Continuous Dynamical Systems, 2004, 11 (2&3) : 581-598. doi: 10.3934/dcds.2004.11.581 |
| [2] |
Stefano Galatolo, Mathieu Hoyrup, Cristóbal Rojas. Dynamics and abstract computability: Computing invariant measures. Discrete and Continuous Dynamical Systems, 2011, 29 (1) : 193-212. doi: 10.3934/dcds.2011.29.193 |
| [3] |
Steven T. Piantadosi. Symbolic dynamics on free groups. Discrete and Continuous Dynamical Systems, 2008, 20 (3) : 725-738. doi: 10.3934/dcds.2008.20.725 |
| [4] |
Jim Wiseman. Symbolic dynamics from signed matrices. Discrete and Continuous Dynamical Systems, 2004, 11 (2&3) : 621-638. doi: 10.3934/dcds.2004.11.621 |
| [5] |
George Osipenko, Stephen Campbell. Applied symbolic dynamics: attractors and filtrations. Discrete and Continuous Dynamical Systems, 1999, 5 (1) : 43-60. doi: 10.3934/dcds.1999.5.43 |
| [6] |
Michael Hochman. A note on universality in multidimensional symbolic dynamics. Discrete and Continuous Dynamical Systems - S, 2009, 2 (2) : 301-314. doi: 10.3934/dcdss.2009.2.301 |
| [7] |
Marc Chamberland, Victor H. Moll. Dynamics of the degree six Landen transformation. Discrete and Continuous Dynamical Systems, 2006, 15 (3) : 905-919. doi: 10.3934/dcds.2006.15.905 |
| [8] |
Jose S. Cánovas, Tönu Puu, Manuel Ruiz Marín. Detecting chaos in a duopoly model via symbolic dynamics. Discrete and Continuous Dynamical Systems - B, 2010, 13 (2) : 269-278. doi: 10.3934/dcdsb.2010.13.269 |
| [9] |
Nicola Soave, Susanna Terracini. Symbolic dynamics for the $N$-centre problem at negative energies. Discrete and Continuous Dynamical Systems, 2012, 32 (9) : 3245-3301. doi: 10.3934/dcds.2012.32.3245 |
| [10] |
Dieter Mayer, Fredrik Strömberg. Symbolic dynamics for the geodesic flow on Hecke surfaces. Journal of Modern Dynamics, 2008, 2 (4) : 581-627. doi: 10.3934/jmd.2008.2.581 |
| [11] |
Fryderyk Falniowski, Marcin Kulczycki, Dominik Kwietniak, Jian Li. Two results on entropy, chaos and independence in symbolic dynamics. Discrete and Continuous Dynamical Systems - B, 2015, 20 (10) : 3487-3505. doi: 10.3934/dcdsb.2015.20.3487 |
| [12] |
David Ralston. Heaviness in symbolic dynamics: Substitution and Sturmian systems. Discrete and Continuous Dynamical Systems - S, 2009, 2 (2) : 287-300. doi: 10.3934/dcdss.2009.2.287 |
| [13] |
Mike Boyle. The work of Mike Hochman on multidimensional symbolic dynamics and Borel dynamics. Journal of Modern Dynamics, 2019, 15: 427-435. doi: 10.3934/jmd.2019026 |
| [14] |
Anke D. Pohl. Symbolic dynamics for the geodesic flow on two-dimensional hyperbolic good orbifolds. Discrete and Continuous Dynamical Systems, 2014, 34 (5) : 2173-2241. doi: 10.3934/dcds.2014.34.2173 |
| [15] |
Nicola Soave, Susanna Terracini. Addendum to: Symbolic dynamics for the $N$-centre problem at negative energies. Discrete and Continuous Dynamical Systems, 2013, 33 (8) : 3825-3829. doi: 10.3934/dcds.2013.33.3825 |
| [16] |
Lorenzo Sella, Pieter Collins. Computation of symbolic dynamics for two-dimensional piecewise-affine maps. Discrete and Continuous Dynamical Systems - B, 2011, 15 (3) : 739-767. doi: 10.3934/dcdsb.2011.15.739 |
| [17] |
Snir Ben Ovadia. Symbolic dynamics for non-uniformly hyperbolic diffeomorphisms of compact smooth manifolds. Journal of Modern Dynamics, 2018, 13: 43-113. doi: 10.3934/jmd.2018013 |
| [18] |
Samuel R. Kaplan, Ernesto A. Lacomba, Jaume Llibre. Symbolic dynamics of the elliptic rectilinear restricted 3--body problem. Discrete and Continuous Dynamical Systems - S, 2008, 1 (4) : 541-555. doi: 10.3934/dcdss.2008.1.541 |
| [19] |
Marian Gidea, Yitzchak Shmalo. Combinatorial approach to detection of fixed points, periodic orbits, and symbolic dynamics. Discrete and Continuous Dynamical Systems, 2018, 38 (12) : 6123-6148. doi: 10.3934/dcds.2018264 |
| [20] |
Yunping Wang, Ercai Chen, Xiaoyao Zhou. Mean dimension theory in symbolic dynamics for finitely generated amenable groups. Discrete and Continuous Dynamical Systems, 2022 doi: 10.3934/dcds.2022050 |
2021 Impact Factor: 1.588
Tools
Metrics
Other articles
by authors
[Back to Top]