Figure 1.
The south west supertile of order two (left) and a representation of petals intersecting its support (right)
-
Previous Article
Parameterized splitting theorems and bifurcations for potential operators, Part II: Applications to quasi-linear elliptic equations and systems
- DCDS Home
- This Issue
-
Next Article
Expansive flows on uniform spaces
doi: 10.3934/dcds.2021143
Online First
Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.
Readers can access Online First articles via the “Online First” tab for the selected journal.
Characterizing entropy dimensions of minimal mutidimensional subshifts of finite type
Faculty of Applied Mathematics, AGH University of Science and Technology, Poland, Krakow, Mickiewicza, A-3/A-4,305 |
In this text I study the asymptotics of the complexity function of minimal multidimensional subshifts of finite type through their entropy dimension, a topological invariant that has been introduced in order to study zero entropy dynamical systems. Following a recent trend in symbolic dynamics I approach this using concepts from computability theory. In particular it is known [
Keywords:
Dynamical systems,
symbolic dynamics,
entropy dimension,
subshifts of finite type,
computability.
Mathematics Subject Classification:
Primary: 37B50, 37B40; Secondary: 37B10, 68Q17.
Citation:
Silvère Gangloff.
Characterizing entropy dimensions of minimal mutidimensional subshifts of finite type. Discrete & Continuous Dynamical Systems, doi: 10.3934/dcds.2021143
![]()
References:
| [1] |
N. Aubrun and M. Sablik,
Multidimensional effective S-adic subshift are sofic, Unif. Distrib. Theory, 9 (2014), 7-29.
|
| [2] |
A. Ballier, Propriétés Structurelles, Combinatoires et Logiques des Pavages, PhD Thesis, Aix-Marseille Université, 2009. Google Scholar |
| [3] |
B. Durand and A. Romashchenko,
On the expressive power of quasiperiodic SFT, 42nd International Symposium on Mathematical Foundations of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 83 (2017), 1-14.
|
| [4] |
B. Durand, L. A. Levin and A. Shen,
Complex tilings, J. Symbolic Logic, 73 (2008), 593-613.
doi: 10.2178/jsl/1208359062. |
| [5] |
S. Gangloff and M. Sablik, Quantified block gluing, aperiodicity and entropy of multidimensional SFT, Journal d'Analyse Mathématique. Google Scholar |
| [6] |
B. Grunbaum and G. C. Shepherd, Tilings and Patterns, W. H. Freeman and Company, New York, 1987. |
| [7] |
M. Hochman and T. Meyerovitch,
A characterization of the entropies of multidimensional shifts of finite type, Ann. of Math., 171 (2010), 2011-2038.
doi: 10.4007/annals.2010.171.2011. |
| [8] |
M. Hochman,
On the dynamics and recursive properties of multidimensional symbolic systems, Invent. Math., 176 (2009), 131-167.
doi: 10.1007/s00222-008-0161-7. |
| [9] |
M. Hochman and P. Vanier,
Turing degree spectra of minimal subshifts, Computer Science - Theory and Applications, Lecture Notes in Comput. Springer, Cham, 10304 (2017), 154-161.
doi: 10.1007/978-3-319-58747-9_15. |
| [10] |
U. Jung, J. Lee and K. Koh Park, Topological entropy dimension and directional entropy dimension for z2-subshifts, Entropy, 19 (2017), 13pp.
doi: 10.3390/e19020046. |
| [11] |
E. Jeandel and P. Vanier,
Characterizations of periods of multidimensional shifts, Ergodic Theory Dynam. Systems, 35 (2015), 431-460.
doi: 10.1017/etds.2013.60. |
| [12] |
T. Meyerovitch,
Growth-type invariants for zd subshifts of finite type and arithmetical classes of real numbers, Invent. Math., 184 (2011), 567-589.
doi: 10.1007/s00222-010-0296-1. |
| [13] |
M. L. Minsky, Computation: Finite and infinite machines, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. |
| [14] |
S. Mozes,
Tilings, substitution systems and dynamical systems generated by them, J. Analyse Math., 53 (1989), 139-186.
doi: 10.1007/BF02793412. |
| [15] |
R. Pavlov and M. Schraudner,
Entropies realizable by block gluing shifts of finite type, J. Anal. Math., 126 (2015), 113-174.
doi: 10.1007/s11854-015-0014-4. |
| [16] |
R. Robinson,
Undecidability and nonperiodicity for tilings of the plane, Invent. Math., 12 (1971), 177-209.
doi: 10.1007/BF01418780. |
show all references
References:
| [1] |
N. Aubrun and M. Sablik,
Multidimensional effective S-adic subshift are sofic, Unif. Distrib. Theory, 9 (2014), 7-29.
|
| [2] |
A. Ballier, Propriétés Structurelles, Combinatoires et Logiques des Pavages, PhD Thesis, Aix-Marseille Université, 2009. Google Scholar |
| [3] |
B. Durand and A. Romashchenko,
On the expressive power of quasiperiodic SFT, 42nd International Symposium on Mathematical Foundations of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 83 (2017), 1-14.
|
| [4] |
B. Durand, L. A. Levin and A. Shen,
Complex tilings, J. Symbolic Logic, 73 (2008), 593-613.
doi: 10.2178/jsl/1208359062. |
| [5] |
S. Gangloff and M. Sablik, Quantified block gluing, aperiodicity and entropy of multidimensional SFT, Journal d'Analyse Mathématique. Google Scholar |
| [6] |
B. Grunbaum and G. C. Shepherd, Tilings and Patterns, W. H. Freeman and Company, New York, 1987. |
| [7] |
M. Hochman and T. Meyerovitch,
A characterization of the entropies of multidimensional shifts of finite type, Ann. of Math., 171 (2010), 2011-2038.
doi: 10.4007/annals.2010.171.2011. |
| [8] |
M. Hochman,
On the dynamics and recursive properties of multidimensional symbolic systems, Invent. Math., 176 (2009), 131-167.
doi: 10.1007/s00222-008-0161-7. |
| [9] |
M. Hochman and P. Vanier,
Turing degree spectra of minimal subshifts, Computer Science - Theory and Applications, Lecture Notes in Comput. Springer, Cham, 10304 (2017), 154-161.
doi: 10.1007/978-3-319-58747-9_15. |
| [10] |
U. Jung, J. Lee and K. Koh Park, Topological entropy dimension and directional entropy dimension for z2-subshifts, Entropy, 19 (2017), 13pp.
doi: 10.3390/e19020046. |
| [11] |
E. Jeandel and P. Vanier,
Characterizations of periods of multidimensional shifts, Ergodic Theory Dynam. Systems, 35 (2015), 431-460.
doi: 10.1017/etds.2013.60. |
| [12] |
T. Meyerovitch,
Growth-type invariants for zd subshifts of finite type and arithmetical classes of real numbers, Invent. Math., 184 (2011), 567-589.
doi: 10.1007/s00222-010-0296-1. |
| [13] |
M. L. Minsky, Computation: Finite and infinite machines, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. |
| [14] |
S. Mozes,
Tilings, substitution systems and dynamical systems generated by them, J. Analyse Math., 53 (1989), 139-186.
doi: 10.1007/BF02793412. |
| [15] |
R. Pavlov and M. Schraudner,
Entropies realizable by block gluing shifts of finite type, J. Anal. Math., 126 (2015), 113-174.
doi: 10.1007/s11854-015-0014-4. |
| [16] |
R. Robinson,
Undecidability and nonperiodicity for tilings of the plane, Invent. Math., 12 (1971), 177-209.
doi: 10.1007/BF01418780. |
Figure 2.
Correspondence between infinite supertiles and sub-patterns of a supertile of finite order
Figure 3.
Schema of the proof. The separating line is colored gray
Figure 4.
Illustration of the definition of the sets $ \mathbb{O}_n $ and $ \mathbb{C}_n $ (respectively dark gray set on the left and on the right)
Figure 5.
Illustration of the construction of the functions $ \varphi_n $
Figure 7.
The set $ \mathbb{O}_k $ can be decomposed into $ 2d $ cuboids. On this picture, $ d = 2 $
Figure 8.
Illustration of the signal transformation in Meyerovitch's construction
Figure 9.
Schema of the proof for the minimality property of $ X_z $
Figure 10.
Orientation of the faces of a three-dimensional cell. The symbols $ h $ and $ v $ indicate respectively the horizontal and vertical directions in each of the copies of the subshift $ X_{\mathcal{R}} $
Figure 11.
Simplified schema of the construction presented in this text. The cube represents a three-dimensional version of the cells observable in the Robinson subshift
Figure 12.
Schema of the functional positions on the faces of a three-dimensional cell
Figure 13.
Schema of the main rule for the orientation sublayer. The squares in the dashed areas are superimposed with the corresponding symbol. The large square at the center is the support petal immediately above in the hierarchy
Figure 14.
Schematic illustration of the rule of the functional areas sublayer. Colors are used as a code for other illustrations
Figure 15.
Pattern over the surface of a three-dimensional cell of order three in the functional areas sublayer. The arrows are oriented according to the fixed orientations of the face
Figure 16.
Schemata of the transformation rules for the vertical addressing. On the two schemata on the left, the central petal has $ p $ -counter value not equal to $ \overline{0} $ . On the two schemata on the right, this value is $ \overline{0} $
Figure 17.
Illustration for the main rule of the horizontal addressing sublayer. The central petals on the two schemata on the left have $ p $ -counter value not equal to $ \overline{0} $ . The one on the schemata on the right have $ p $ -counter value equal to $ \overline{0} $
Figure 18.
Illustration for the active functional areas sublayer on a two-dimensional cell over the face of a three-dimensional cell, with $ p = 3 $ . The addresses of active columns and and all the rows are represented
Figure 19.
Notations for the faces of three-dimensional cells
Figure 20.
Localization of the machine symbols on the bottom faces of the cubes, according to the direction $ {\bf{e}}^3 $ . Blue columns (resp. rows) symbolize computation-active columns (resp. rows)
Figure 21.
Schema of the inputs and outputs directions when inside the area (1) and on the border of the area (2, 3, 4, 5, 6)
Figure 22.
Illustration of the standard rules (1)
Figure 23.
Illustration of the standard rules (2)
Figure 24.
Illustration of the propagation rule of the error signal, where are represented the empty tape, first machine and empty sides signals
Figure 25.
Illustration of the transformation rules of the hierarchy bits when the grouping bit is $ 1 $
Figure 26.
Illustration of the completion of the $ \texttt{on}/\texttt{off} $ signals and the space-time diagram of the machine. The known part is surrounded by a black square
Figure 27.
Illustration of the completion of the arrows according to the error signal in the known part of the area, designated by a dashed rectangle
Figure 28.
Schema of the proof for the minimality property of $ X_z $
Figure 29.
Illustration of the convolutions rules
Figure 30.
Possible orientations of four neighbor supertiles having the same order (1)
Figure 31.
Possible orientations of four neighbor supertiles having the same order (2)
Figure 32.
Possible orientations of four neighbor supertiles having the same order (3)
| [1] |
Christopher Hoffman. Subshifts of finite type which have completely positive entropy. Discrete & Continuous Dynamical Systems, 2011, 29 (4) : 1497-1516. doi: 10.3934/dcds.2011.29.1497 |
| [2] |
Felix X.-F. Ye, Hong Qian. Stochastic dynamics Ⅱ: Finite random dynamical systems, linear representation, and entropy production. Discrete & Continuous Dynamical Systems - B, 2019, 24 (8) : 4341-4366. doi: 10.3934/dcdsb.2019122 |
| [3] |
Wen-Guei Hu, Song-Sun Lin. On spatial entropy of multi-dimensional symbolic dynamical systems. Discrete & Continuous Dynamical Systems, 2016, 36 (7) : 3705-3717. doi: 10.3934/dcds.2016.36.3705 |
| [4] |
Xiaomin Zhou. Relative entropy dimension of topological dynamical systems. Discrete & Continuous Dynamical Systems, 2019, 39 (11) : 6631-6642. doi: 10.3934/dcds.2019288 |
| [5] |
Silvére Gangloff, Alonso Herrera, Cristobal Rojas, Mathieu Sablik. Computability of topological entropy: From general systems to transformations on Cantor sets and the interval. Discrete & Continuous Dynamical Systems, 2020, 40 (7) : 4259-4286. doi: 10.3934/dcds.2020180 |
| [6] |
Fryderyk Falniowski, Marcin Kulczycki, Dominik Kwietniak, Jian Li. Two results on entropy, chaos and independence in symbolic dynamics. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3487-3505. doi: 10.3934/dcdsb.2015.20.3487 |
| [7] |
David Ralston. Heaviness in symbolic dynamics: Substitution and Sturmian systems. Discrete & Continuous Dynamical Systems - S, 2009, 2 (2) : 287-300. doi: 10.3934/dcdss.2009.2.287 |
| [8] |
Jérôme Rousseau, Paulo Varandas, Yun Zhao. Entropy formulas for dynamical systems with mistakes. Discrete & Continuous Dynamical Systems, 2012, 32 (12) : 4391-4407. doi: 10.3934/dcds.2012.32.4391 |
| [9] |
Yujun Zhu. Preimage entropy for random dynamical systems. Discrete & Continuous Dynamical Systems, 2007, 18 (4) : 829-851. doi: 10.3934/dcds.2007.18.829 |
| [10] |
H. M. Hastings, S. Silberger, M. T. Weiss, Y. Wu. A twisted tensor product on symbolic dynamical systems and the Ashley's problem. Discrete & Continuous Dynamical Systems, 2003, 9 (3) : 549-558. doi: 10.3934/dcds.2003.9.549 |
| [11] |
Silvère Gangloff, Benjamin Hellouin de Menibus. Effect of quantified irreducibility on the computability of subshift entropy. Discrete & Continuous Dynamical Systems, 2019, 39 (4) : 1975-2000. doi: 10.3934/dcds.2019083 |
| [12] |
Dou Dou. Minimal subshifts of arbitrary mean topological dimension. Discrete & Continuous Dynamical Systems, 2017, 37 (3) : 1411-1424. doi: 10.3934/dcds.2017058 |
| [13] |
Yun Zhao, Wen-Chiao Cheng, Chih-Chang Ho. Q-entropy for general topological dynamical systems. Discrete & Continuous Dynamical Systems, 2019, 39 (4) : 2059-2075. doi: 10.3934/dcds.2019086 |
| [14] |
Stefano Galatolo, Mathieu Hoyrup, Cristóbal Rojas. Dynamics and abstract computability: Computing invariant measures. Discrete & Continuous Dynamical Systems, 2011, 29 (1) : 193-212. doi: 10.3934/dcds.2011.29.193 |
| [15] |
Steven T. Piantadosi. Symbolic dynamics on free groups. Discrete & Continuous Dynamical Systems, 2008, 20 (3) : 725-738. doi: 10.3934/dcds.2008.20.725 |
| [16] |
Kazuhiro Kawamura. Mean dimension of shifts of finite type and of generalized inverse limits. Discrete & Continuous Dynamical Systems, 2020, 40 (8) : 4767-4775. doi: 10.3934/dcds.2020200 |
| [17] |
David Burguet, Todd Fisher. Symbolic extensionsfor partially hyperbolic dynamical systems with 2-dimensional center bundle. Discrete & Continuous Dynamical Systems, 2013, 33 (6) : 2253-2270. doi: 10.3934/dcds.2013.33.2253 |
| [18] |
Igor E. Shparlinski. On some dynamical systems in finite fields and residue rings. Discrete & Continuous Dynamical Systems, 2007, 17 (4) : 901-917. doi: 10.3934/dcds.2007.17.901 |
| [19] |
Yixiao Qiao, Xiaoyao Zhou. Zero sequence entropy and entropy dimension. Discrete & Continuous Dynamical Systems, 2017, 37 (1) : 435-448. doi: 10.3934/dcds.2017018 |
| [20] |
Yuan-Ling Ye. Non-uniformly expanding dynamical systems: Multi-dimension. Discrete & Continuous Dynamical Systems, 2019, 39 (5) : 2511-2553. doi: 10.3934/dcds.2019106 |
2020 Impact Factor: 1.392
Tools
Metrics
Other articles
by authors
[Back to Top]