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