Top

Published in:

2018 | OriginalPaper | Chapter

Slopes of 3-Dimensional Subshifts of Finite Type

Authors : Etienne Moutot, Pascal Vanier

Published in: Computer Science – Theory and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper we study the directions of periodicity of three-dimensional subshifts of finite type (SFTs) and in particular their slopes. A configuration of a subshift has a slope of periodicity if it is periodic in exactly one direction, the slope being the angles of the periodicity vector. In this paper, we prove that any \(\varSigma ^0_2\) set may be realized as a a set of slopes of an SFT.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Max-Cut Above Spanning Tree is Fixed-Parameter Tractable

next chapter Facility Location on Planar Graphs with Unreliable Links

Aubrun, N., Sablik, M.: Simulation of effective subshifts by two-dimensional subshifts of finite type. Acta Applicandae Math. 126(1), 35–63 (2013)MathSciNetCrossRefMATH

Berger, R.: The Undecidability of the Domino Problem. Ph.D. thesis, Harvard University (1964)

Berger, R.: The Undecidability of the Domino Problem. No. 66 in Memoirs of the American Mathematical Society, The American Mathematical Society (1966)MathSciNetCrossRef

Culik II, K., Kari, J.: An aperiodic set of Wang cubes. J. Univers. Comput. Sci. 1(10), 675–686 (1995)MathSciNetMATH

Durand, B., Romashchenko, A., Shen, A.: Fixed-point tile sets and their applications. J. Comput. Syst. Sci. 78(3), 731–764 (2012)MathSciNetCrossRefMATH

Gurevich, Y., Koryakov, I.: Remarks on Berger’s paper on the domino problem. Siberian Math. J. 13(2), 319–320 (1972)CrossRefMATH

Hochman, M., Meyerovitch, T.: A characterization of the entropies of multidimensional shifts of finite type. Ann. Math. 171(3), 2011–2038 (2010)MathSciNetCrossRefMATH

Jeandel, E., Rao, M.: An aperiodic set of 11 Wang tiles. CoRR abs/1506.06492 (2015). http://arxiv.org/abs/1506.06492

Jeandel, E., Vanier, P.: Slopes of tilings. In: Kari, J. (ed.) JAC, pp. 145–155. Turku Center for Computer Science (2010)

10.

Jeandel, E., Vanier, P.: Characterizations of periods of multi-dimensional shifts. Ergod. Theor. Dyn. Syst. 35(2), 431–460 (2015). http://journals.cambridge.org/article_S0143385713000606MathSciNetCrossRefMATH

11.

Kari, J.: The nilpotency problem of one-dimensional cellular automata. SIAM J.Comput. 21(3), 571–586 (1992)MathSciNetCrossRefMATH

12.

Kari, J.: A small aperiodic set of Wang tiles. Discrete Math. 160(1–3), 259–264 (1996)MathSciNetCrossRefMATH

13.

Lind, D.A., Marcus, B.: An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, New York (1995)CrossRefMATH

14.

Meyerovitch, T.: Growth-type invariants for \(\mathbb{Z}^d\) subshifts of finite type and arithmetical classes of real numbers. Inventiones Math. 184(3), 567–589 (2010)MathSciNetCrossRef

15.

Myers, D.: Non recursive tilings of the plane II. J. Symbolic Log. 39(2), 286–294 (1974)MathSciNetCrossRefMATH

16.

Ollinger, N.: Two-by-two substitution systems and the undecidability of the domino problem. In: Beckmann, A., Dimitracopoulos, C., Löwe, B. (eds.) CiE 2008. LNCS, vol. 5028, pp. 476–485. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-69407-6_51CrossRefMATH

17.

Poupet, V.: Yet another aperiodic tile set. In: Journées Automates Cellulaires (JAC), pp. 191–202. TUCS (2010)

18.

Robinson, R.M.: Undecidability and nonperiodicity for tilings of the plane. Inventiones Math. 12(3), 177–209 (1971)MathSciNetCrossRefMATH

19.

Rogers Jr., H.: Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge (1987)MATH

20.

Wang, H.: Proving theorems by pattern recognition I. Commun. ACM 3(4), 220–234 (1960)CrossRefMATH

Title: Slopes of 3-Dimensional Subshifts of Finite Type
Authors: Etienne Moutot
Pascal Vanier
Publisher: Springer International Publishing
Book: Computer Science – Theory and Applications
Print ISBN: 978-3-319-90529-7

Electronic ISBN: 978-3-319-90530-3

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-90530-3_22

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner