April  2021, 41(4): 1627-1648. doi: 10.3934/dcds.2020334

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

Received  October 2019 Revised  July 2020 Published  April 2021 Early access  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.

Citation: Ronnie Pavlov, Pascal Vanier. The relationship between word complexity and computational complexity in subshifts. Discrete and Continuous Dynamical Systems, 2021, 41 (4) : 1627-1648. 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.

[2]

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

[3]

E. CovenA. JohnsonN. 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. CovenA. JohnsonN. 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

Metrics

  • PDF downloads (189)
  • HTML views (168)
  • Cited by (0)

Other articles
by authors

[Back to Top]