American Institute of Mathematical Sciences

Advanced
  • 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

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]

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

Tools

Article outline

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences