# American Institute of Mathematical Sciences

• Previous Article
Boundary asymptotics of the ergodic functions associated with fully nonlinear operators through a Liouville type theorem
• DCDS Home
• This Issue
• Next Article
Dynamics of the 2D Navier-Stokes equations with sublinear operators in Lipschitz-like domains
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  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 & 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] Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167 [2] Evan Greif, Daniel Kaplan, Robert S. Strichartz, Samuel C. Wiese. Spectrum of the Laplacian on regular polyhedra. Communications on Pure & Applied Analysis, 2021, 20 (1) : 193-214. doi: 10.3934/cpaa.2020263 [3] Stefan Ruschel, Serhiy Yanchuk. The spectrum of delay differential equations with multiple hierarchical large delays. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 151-175. doi: 10.3934/dcdss.2020321 [4] Yoshihisa Morita, Kunimochi Sakamoto. Turing type instability in a diffusion model with mass transport on the boundary. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3813-3836. doi: 10.3934/dcds.2020160 [5] Xianyong Chen, Weihua Jiang. Multiple spatiotemporal coexistence states and Turing-Hopf bifurcation in a Lotka-Volterra competition system with nonlocal delays. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021013 [6] Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007 [7] Neng Zhu, Zhengrong Liu, Fang Wang, Kun Zhao. Asymptotic dynamics of a system of conservation laws from chemotaxis. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 813-847. doi: 10.3934/dcds.2020301 [8] Jong-Shenq Guo, Ken-Ichi Nakamura, Toshiko Ogiwara, Chang-Hong Wu. The sign of traveling wave speed in bistable dynamics. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3451-3466. doi: 10.3934/dcds.2020047 [9] Yueh-Cheng Kuo, Huey-Er Lin, Shih-Feng Shieh. Asymptotic dynamics of hermitian Riccati difference equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020365 [10] Yu Jin, Xiang-Qiang Zhao. The spatial dynamics of a Zebra mussel model in river environments. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020362 [11] Hua Shi, Xiang Zhang, Yuyan Zhang. Complex planar Hamiltonian systems: Linearization and dynamics. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020406 [12] Weiwei Liu, Jinliang Wang, Yuming Chen. Threshold dynamics of a delayed nonlocal reaction-diffusion cholera model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020316 [13] Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045 [14] Cuicui Li, Lin Zhou, Zhidong Teng, Buyu Wen. The threshold dynamics of a discrete-time echinococcosis transmission model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020339 [15] Shao-Xia Qiao, Li-Jun Du. Propagation dynamics of nonlocal dispersal equations with inhomogeneous bistable nonlinearity. Electronic Research Archive, , () : -. doi: 10.3934/era.2020116 [16] Ebraheem O. Alzahrani, Muhammad Altaf Khan. Androgen driven evolutionary population dynamics in prostate cancer growth. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020426 [17] Zhimin Li, Tailei Zhang, Xiuqing Li. Threshold dynamics of stochastic models with time delays: A case study for Yunnan, China. Electronic Research Archive, 2021, 29 (1) : 1661-1679. doi: 10.3934/era.2020085 [18] Rong Wang, Yihong Du. Long-time dynamics of a diffusive epidemic model with free boundaries. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020360 [19] Linfeng Mei, Feng-Bin Wang. Dynamics of phytoplankton species competition for light and nutrient with recycling in a water column. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020359 [20] Chang-Yuan Cheng, Shyan-Shiou Chen, Rui-Hua Chen. Delay-induced spiking dynamics in integrate-and-fire neurons. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020363

2019 Impact Factor: 1.338