Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-28T00:06:21.986Z Has data issue: false hasContentIssue false
  • English
  • Français

Characterizations of periods of multi-dimensional shifts

Published online by Cambridge University Press:  27 September 2013

EMMANUEL JEANDEL  and
PASCAL VANIER
EMMANUEL JEANDEL
Affiliation:
LORIA, Campus Scientifique, BP 239, 54506 Vandoeuvre-lès-Nancy, France email [email protected]
PASCAL VANIER
Affiliation:
Einstein Institute of Mathematics, Hebrew University of Jerusalem, Givat Ram, Jerusalem 91904, Israel email [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that the sets of periods of multi-dimensional shifts of finite type are precisely the sets of integers of the complexity class NP. We also show that the functions counting their number are the functions of #P. We also give characterizations of some other notions of periodicity in terms of space complexity. We finish the paper by giving some characterizations for sofic and effective subshifts.

Type
Research Article
Information
Ergodic Theory and Dynamical Systems , Volume 35 , Issue 2 , April 2015 , pp. 431 - 460
Copyright
© Cambridge University Press, 2013 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Arora, S. and Barak, B.. Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge, 2009.CrossRefGoogle Scholar
Aubrun, N. and Sablik, M.. An order on sets of tilings corresponding to an order on languages. 26th Int. Symp. on Theoretical Aspects of Computer Science (Leibniz Int. Proc. in Informatics, 3). Eds. Albers, S. and Marion, J.-Y.. Schloss Dagstuhl–Leibniz Zentrum für Informatik, Dagstuhl, Germany, 2009, pp. 99–110.Google Scholar
Aubrun, N. and Sablik, M.. Simulation of effective subshifts by two-dimensional SFT and a generalization. Acta Appl. Math. (2013), to appear.Google Scholar
Balcazar, J., Diaz, J. and Gabarro, J.. Structural Complexity I. Springer, Berlin, 1988.CrossRefGoogle Scholar
Berger, R.. The undecidability of the domino problem. PhD Thesis, Harvard University, 1964.Google Scholar
Berger, R.. The Undecidability of the Domino Problem (Memoirs of the American Mathematical Society, 66). American Mathematical Society, Providence, RI, 1966.CrossRefGoogle Scholar
Berstel, J.. Axel Thue’s papers on repetitions in words: a translation. Publications du LaCIM 20 (1995).Google Scholar
Borchert, B.. Formal language characterizations of P, NP, and PSPACE. J. Autom. Lang. Comb. 13 (3/4) (2008), 161–183.Google Scholar
Chaitin, G.. The halting probability via Wang tiles. Fund. Inform. 86 (4) (2008), 429–433.Google Scholar
Carayol, A. and Meyer, A.. Context-sensitive languages, rational graphs and determinism. Log. Methods Comput. Sci. (2006), 1–24.Google Scholar
Durand, A., Jones, N. D., Makowsky, J. A. and More, M.. Fifty years of the spectrum problem: survey and new results. Preprint, arXiv:0907.5495v1.Google Scholar
Durand, B., Romashchenko, A. and Shen, A.. Effective closed subshifts in 1D can be implemented in 2D. Fields of Logic and Computation (Lecture Notes in Computer Science, 6300). Springer, Berlin, 2010, pp. 208–226.Google Scholar
van Emde Boas, P.. Machine models and simulations. Handbook of Theoretical Computer Science vol A: Algorithms and Complexity. Ed. Leeuwen, J. V.. MIT Press, Cambridge, MA, 1990, pp. 1–66; Ch. 1.Google Scholar
Flores, I.. Reflected number systems. IRE Trans. Electron. Comput. 5 (2) (1956), 79–82.CrossRefGoogle Scholar
Hochman, M. and Meyerovitch, T.. A characterization of the entropies of multidimensional shifts of finite type. Ann. Math. (2) 171 (3) (2010), 2011–2038.Google Scholar
Immerman, N.. Nondeterministic space is closed under complementation. SIAM J. Comput. 17 (5) (1988), 935–938.Google Scholar
Jones, N. D. and Selman, A. L.. Turing machines and the spectra of first-order formulas. J. Symbolic Logic 39 (1) (1974), 139–150.Google Scholar
Jeandel, E. and Vanier, P.. Periodicity in tilings. Developments in Language Theory (Lecture Notes in Computer Science, 6224). Eds. Gao, Y., Lu, H., Seki, S. and Yu, S.. Springer, Berlin, 2010, pp. 243–254.CrossRefGoogle Scholar
Kari, J.. The nilpotency problem of one-dimensional cellular automata. SIAM J. Comput. 21 (3) (1992), 571–586.Google Scholar
Kari, J.. Reversibility and surjectivity problems of cellular automata. J. Comput. Syst. Sci. 48 (1) (1994), 149–182.Google Scholar
Kari, J.. A small aperiodic set of Wang tiles. Discrete Math. 160 (1996), 259–264.Google Scholar
Knuth, D. E.. Generating all tuples and permutations. The Art of Computer Programming. Vol. 4 Fasc. 2. Addison-Wesley, Upper Saddle River, NJ, 2005.Google Scholar
Lind, D.. Multidimensional symbolic dynamics. Symbolic Dynamics and Its Applications (Proceedings of Symposia in Applied Mathematics, 60). Ed. Williams, S. G.. American Mathematical Society, San Diego, CA, 2004, pp. 61–80.Google Scholar
Lind, D.. A zeta function for ${ \mathbb{Z} }^{d} $-actions. Proceedings of Warwick Symposium on ${ \mathbb{Z} }^{d} $actions (LMS Lecture Notes Series, 228). Cambride University Press, Cambridge, 1996, pp. 433–450.Google Scholar
Lind, D. A. and Marcus, B.. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, New York, 1995.CrossRefGoogle Scholar
Morse, H. M.. Recurrent geodesics on a surface of negative curvature. Trans. Amer. Math. Soc. 22 (1) (1921), 84–100.Google Scholar
Robinson, R. M.. Undecidability and nonperiodicity for tilings of the plane. Invent. Math. 12 (1971).Google Scholar
Rogers, H.. Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge, MA, 1987.Google Scholar
Simpson, S. G.. Medvedev degrees of 2-dimensional subshifts of finite type. Ergod. Th. & Dynam. Sys. (2012).Google Scholar
Szelepcsényi, R.. The method of forcing for nondeterministic automata. Bull. EATCS 33 (1987), 96–100.Google Scholar
Thue, A.. Über die gegenseitige Lage gleicher Teiler gewisser Zeichenreihen. Kra. Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl. 12 (1912), transl. in [Ber95].Google Scholar