The relationship between word complexity and computational complexity in subshifts

Ronnie Pavlov; Pascal Vanier

doi:10.3934/dcds.2020334

Article Contents

2021, Volume 41, Issue 4: 1627-1648. Doi: 10.3934/dcds.2020334

This issue Previous Article Classification of nonnegative solutions to an equation involving the Laplacian of arbitrary order Next Article Recurrence for measurable semigroup actions

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: September 30, 2019

Revised: June 30, 2020

Early access: October 2020

Published: April 2021

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

Abstract Full Text(HTML) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 37B10; Secondary: 03D15, 03D25.

Citation:

Full Text(HTML)

Related Papers

Cited by

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.