×

zbMATH — the first resource for mathematics

Characterizations of periods of multi-dimensional shifts. (English) Zbl 1336.37015
Following recent works that characterize dynamical invariants of multi-dimensional shifts of finite type (SFT) in computability-theoretical terms, this article gives dynamical characterizations with the original help of complexity theory.
Namely, if numbers are all represented unarily:
*
the sets of strong periods of SFT are exactly those in \(\mathsf{NP}_1\) (unary languages decidable in polynomial time by a nondeterministic Turing machine);
*
the sets of horizontal periods of SFT are exactly those in \(\mathsf{NSPACE}_1(n)\) (unary languages decidable in linear space by a nondeterministic Turing machine);
*
the sets of periodicity vectors of 2D SFT are exactly the sets of pairs of integers in \(\mathsf{NSPACE}_1(n)\);
*
the sets of functions counting the points that have a given strong period, in SFT, are exactly those in \(\#\mathsf{P}\) (counting accepting paths in a nondeterministic polynomial-time computation).
In contrast, it is eventually shown that the sets of periodicity vectors for effective or sofic subshifts are exactly the sets in \(\Pi^0_1\) (co-recursively enumerable).
The constructions involve a smart combination classical marking widgets, a Turing machine embedding, and an aperiodic deterministic tile set.

MSC:
37B50 Multi-dimensional shifts of finite type, tiling dynamics (MSC2010)
37E15 Combinatorial dynamics (types of periodic orbits)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Berstel, Publications du LaCIM 20 (1995)
[2] Borchert, J. Autom. Lang. Comb. 13 pp 161– (2008)
[3] DOI: 10.4007/annals.2010.171.2011 · Zbl 1192.37022 · doi:10.4007/annals.2010.171.2011
[4] Berger, The Undecidability of the Domino Problem (1966) · Zbl 0199.30802
[5] van Emde Boas, Handbook of Theoretical Computer Science vol A: Algorithms and Complexity pp 1– (1990) · Zbl 0900.68265
[6] DOI: 10.1007/978-3-642-15025-8_12 · Zbl 1287.37012 · doi:10.1007/978-3-642-15025-8_12
[7] DOI: 10.1007/978-3-642-97062-7 · doi:10.1007/978-3-642-97062-7
[8] Carayol, Log. Methods Comput. Sci. pp 1– (2006)
[9] Aubrun, 26th Int. Symp. on Theoretical Aspects of Computer Science pp 99– (2009)
[10] DOI: 10.1017/CBO9780511804090 · Zbl 1193.68112 · doi:10.1017/CBO9780511804090
[11] Simpson, Ergod. Th. & Dynam. Sys. (2012)
[12] Rogers, Theory of Recursive Functions and Effective Computability (1987)
[13] DOI: 10.1007/BF01418780 · Zbl 0197.46801 · doi:10.1007/BF01418780
[14] DOI: 10.1090/S0002-9947-1921-1501161-8 · doi:10.1090/S0002-9947-1921-1501161-8
[15] DOI: 10.1017/CBO9780511626302 · Zbl 1106.37301 · doi:10.1017/CBO9780511626302
[16] DOI: 10.1090/psapm/060/2078846 · doi:10.1090/psapm/060/2078846
[17] DOI: 10.1016/0012-365X(95)00120-L · Zbl 0861.05017 · doi:10.1016/0012-365X(95)00120-L
[18] DOI: 10.1016/S0022-0000(05)80025-X · Zbl 0802.68090 · doi:10.1016/S0022-0000(05)80025-X
[19] Knuth, The Art of Computer Programming. Vol. 4 Fasc. 2 (2005) · Zbl 1127.68068
[20] Thue, Kra. Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl. 12 (1912)
[21] SzelepcsĂ©nyi, Bull. EATCS 33 pp 96– (1987)
[22] DOI: 10.1137/0221036 · Zbl 0761.68067 · doi:10.1137/0221036
[23] DOI: 10.1007/978-3-642-14455-4_23 · Zbl 1250.68109 · doi:10.1007/978-3-642-14455-4_23
[24] DOI: 10.2307/2272354 · Zbl 0288.02021 · doi:10.2307/2272354
[25] Chaitin, Fund. Inform. 86 pp 429– (2008)
[26] DOI: 10.1137/0217058 · Zbl 0668.68056 · doi:10.1137/0217058
[27] DOI: 10.1109/TEC.1956.5219803 · doi:10.1109/TEC.1956.5219803
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.