American Institute of Mathematical Sciences

Advanced
doi: 10.3934/dcds.2020334

The relationship between word complexity and computational complexity in subshifts

Ronnie Pavlov 1, and  Pascal Vanier 2,

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

Received  October 2019 Revised  July 2020 Published  October 2020

Fund Project: The first author gratefully acknowledges the support of NSF grant DMS-1500685. The second author gratefully acknowledges the support of ANR grants ANR-12-BS02-0007 and 19-CE48-0007- 01

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.

Keywords: Symbolic dynamics, Turing degree, word complexity, computability, spectrum.
Mathematics Subject Classification: Primary: 37B10; Secondary: 03D15, 03D25.
Citation: Ronnie Pavlov, Pascal Vanier. The relationship between word complexity and computational complexity in subshifts. Discrete & Continuous Dynamical Systems - A, doi: 10.3934/dcds.2020334
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.  Google Scholar

[2]

S. B. Cooper, Computability Theory, Chapman & Hall/CRC Mathematics Series, Chapman & Hall/CRC, 2004.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8]

M. Lothaire, Algebraic Combinatorics on Words, 2002. doi: 10.1017/CBO9780511566097.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

H. Rogers, Theory of Recursive Functions and Effective Computability, MIT Press Cambridge, MA, USA, 1987.  Google Scholar

[12]

P. Walters, An Introduction to Ergodic Theory, Graduate Texts in Mathematics, 79, Springer, 1982.  Google Scholar

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.  Google Scholar

[2]

S. B. Cooper, Computability Theory, Chapman & Hall/CRC Mathematics Series, Chapman & Hall/CRC, 2004.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8]

M. Lothaire, Algebraic Combinatorics on Words, 2002. doi: 10.1017/CBO9780511566097.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

H. Rogers, Theory of Recursive Functions and Effective Computability, MIT Press Cambridge, MA, USA, 1987.  Google Scholar

[12]

P. Walters, An Introduction to Ergodic Theory, Graduate Texts in Mathematics, 79, Springer, 1982.  Google Scholar

[1]

Frédéric Naud. Birkhoff cones, symbolic dynamics and spectrum of transfer operators. Discrete & Continuous Dynamical Systems - A, 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 & Continuous Dynamical Systems - A, 2011, 29 (1) : 193-212. doi: 10.3934/dcds.2011.29.193
[3]

Steven T. Piantadosi. Symbolic dynamics on free groups. Discrete & Continuous Dynamical Systems - A, 2008, 20 (3) : 725-738. doi: 10.3934/dcds.2008.20.725
[4]

Jim Wiseman. Symbolic dynamics from signed matrices. Discrete & Continuous Dynamical Systems - A, 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 & Continuous Dynamical Systems - A, 1999, 5 (1) : 43-60. doi: 10.3934/dcds.1999.5.43
[6]

Michael Hochman. A note on universality in multidimensional symbolic dynamics. Discrete & 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 & Continuous Dynamical Systems - A, 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 & 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 & Continuous Dynamical Systems - A, 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 & 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 & 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 & Continuous Dynamical Systems - A, 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 & Continuous Dynamical Systems - A, 2013, 33 (8) : 3825-3829. doi: 10.3934/dcds.2013.33.3825
[16]

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
[17]

Lorenzo Sella, Pieter Collins. Computation of symbolic dynamics for two-dimensional piecewise-affine maps. Discrete & Continuous Dynamical Systems - B, 2011, 15 (3) : 739-767. doi: 10.3934/dcdsb.2011.15.739
[18]

Samuel R. Kaplan, Ernesto A. Lacomba, Jaume Llibre. Symbolic dynamics of the elliptic rectilinear restricted 3--body problem. Discrete & 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 & Continuous Dynamical Systems - A, 2018, 38 (12) : 6123-6148. doi: 10.3934/dcds.2018264
[20]

Martha G. Alatriste-Contreras, Juan Gabriel Brida, Martin Puchet Anyul. Structural change and economic dynamics: Rethinking from the complexity approach. Journal of Dynamics & Games, 2019, 6 (2) : 87-106. doi: 10.3934/jdg.2019007

2019 Impact Factor: 1.338

Tools

Article outline

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences