Effective S-adic Symbolic Dynamical Systems

详细信息    查看全文

• 关键词：Symbolic dynamics ; Adic map ; Substitution ; S ; adic system ; Planar tiling ; Local rules ; Sofic subshift ; Subshift of finite type ; Computable invariant measure ; Effective language
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9709
• 期：1
• 页码：13-23
• 全文大小：205 KB
• 参考文献：1.Arnoux, P., Ito, S.: Pisot substitutions and Rauzy fractals. Bull. Belg. Math. Soc. Simon Stevin 8, 181–207 (2001)MathSciNet MATH
  2.Aubrun, N., Sablik, M.: Multidimensional effective S-adic systems are sofic. Distrib. Theor. 9, 7–29 (2014)MathSciNet MATH
  3.Aubrun, N., Sablik, M.: Simulation of effective subshifts by two-dimensional subshifts of finite type. Acta Applicandae Mathematicae 126, 35–63 (2013)MathSciNet CrossRef MATH
  4.Baake, M., Grimm, U.: Aperiodic Order: A Mathematical Invitation, vol. 1. Cambridge University Press, Cambridge (2013)CrossRef MATH
  5.Bédaride, N., Fernique, T.: No weak local rules for the \(4p\) -fold tilings. Disc. Comput. Geom. 54, 980–992 (2015)MathSciNet CrossRef MATH
  6.Bédaride, N., Fernique, T.: When periodicities enforce aperiodicity. Commun. Math. Phys. 335, 1099–1120 (2015)MathSciNet CrossRef MATH
  7.Bell, J.P., Charlier, E., Fraenkel, A.S., Rigo, M.: A decision problem for ultimately periodic sets in non-standard numeration systems. Int. J. Algebra Comput. 9, 809–839 (2009)MathSciNet CrossRef MATH
  8.Berger, R.: The Undecidability of the Domino Problem, vol. 66. Memoirs of the American Mathematical Society, Providence (1966)MATH
  9.Berthé, V., Delecroix, V.: Beyond substitutive dynamical systems: S-adic expansions, RIMS Lecture note ‘Kokyuroku Bessatu’ B46, pp. 81–123 (2014)
  10.Berthé, V., Rigo, M. (eds.): Combinatorics, Automata and Number Theory, Encyclopedia of Mathematics and its Applications, vol. 135. Cambridge University Press, Cambridge (2010)
  11.Berthé, V., Rigo, M. (eds.): Combinatorics, Words and Symbolic dynamics, Encyclopedia of Mathematics and its Applications, vol. 159. Cambridge University Press, Cambridge (2016)
  12.Berthé, V., Vuillon, L.: Tilings and rotations on the torus: a two-dimensional generalization of Sturmian sequences. Discrete Math. 223, 27–53 (2000)MathSciNet CrossRef MATH
  13.Berthé, V., Bourdon, J., Jolivet, T., Siegel, A.: Generating discrete planes with substitutions. In: Karhumäki, J., Lepistö, A., Zamboni, L. (eds.) WORDS 2013. LNCS, vol. 8079, pp. 58–70. Springer, Heidelberg (2013)CrossRef
  14.Bienvenu, L., Day, A.R., Hoyrup, M., Mezhirov, I., Shen, A.: A constructive version of Birkhoff’s ergodic theorem for Martin-Löf random points. Inf. Comput. 210, 21–30 (2012)MathSciNet CrossRef MATH
  15.Bruyère, V., Hansel, G., Michaux, C., Villemaire, R.: Logic and \(p\) -recognizable sets of integers. Bull. Belg. Math. Soc. Simon Stevin 12, 191–238. Correction to: “Logic and \(p\) -recognizable sets of integers”. Bull. Belg. Math. Soc. Simon Stevin 14, 577 (1994)
  16.Charlier, E., Kärki, T., Rigo, M.: Multidimensional generalized automatic sequences and shape-symmetric morphic words. Discrete Math. 310, 1238–1252 (2010)MathSciNet CrossRef MATH
  17.Charlier, E., Rampersad, N., Shallit, J.: Enumeration and decidable properties of automatic sequences. Int. J. Found. Comput. Sci. 23, 1035–1066 (2012)MathSciNet CrossRef MATH
  18.de Bruijn, N.G.: Algebraic theory of Penrose’s nonperiodic tilings of the plane. Nederl. Akad. Wetensch. Indag. Math. 43, 39–66 (1981)MathSciNet CrossRef MATH
  19.Durand, B., Romashchenko, A.E., Shen, A.: Effective closed subshifts in 1D can be implemented in 2D. In: Blass, A., Dershowitz, N., Reisig, W. (eds.) Fields of Logic and Computation. LNCS, vol. 6300, pp. 208–226. Springer, Heidelberg (2010)CrossRef
  20.Durand, F.: Linearly recurrent subshifts have a finite number of non-periodic subshift factors, Ergodic Theor. Dynam. Syst. 20, 1061–1078. Corrigendum and addendum, Ergodic Theor. Dynam. Syst. 23, 663–669 (2003)
  21.Durand, F.: HD0L \(\omega \) -equivalence and periodicity problems in the primitive case. Unif. Distrib. Theor. 7(1), 199–215 (2012)MathSciNet MATH
  22.Durand, F.: Decidability of the HD0L ultimate periodicity problem. RAIRO - Theor. Inf. Appl. 47, 201–214 (2013)MathSciNet CrossRef MATH
  23.Durand, F.: Decidability of uniform recurrence of morphic sequences. Int. J. Found. Comput. Sci. 24, 123–146 (2013)MathSciNet CrossRef MATH
  24.Durand, F., Host, B., Skau, C.: Substitutional dynamical systems, Bratteli diagrams and dimension groups. Ergodic Theor. Dyn. Syst. 19(4), 953–993 (1999)MathSciNet CrossRef MATH
  25.Fernique, T.: Local rule substitutions and stepped surfaces. Theor. Comput. Sci. 380, 317–329 (2007)MathSciNet CrossRef MATH
  26.Fernique, T., Ollinger, N.: Combinatorial substitutions and sofic tilings. In: JAC (2010)
  27.Fernique, T., Sablik, M.: Local rules for computable planar tilings automata. In: JAC (2012)
  28.Frank, N.P.: A primer of substitution tilings of the Euclidean plane. Expo. Math. 26, 295–326 (2008)MathSciNet CrossRef MATH
  29.Frank, N.P., Sadun, L.: Fusion: a general framework for hierarchical tilings of Rd. Geom. Dedicata. 171, 149–186 (2014)MathSciNet CrossRef MATH
  30.Gangloff, S., de Menibus, B.H.: Computing the entropy of one-dimensional decidable subshifts. arXiv:​1602.​06166
  31.Goodman-Strauss, C.: Matching rules and substitution tilings. Ann. Math. 147, 181–223 (1998)MathSciNet CrossRef MATH
  32.Herman, R.H., Putnam, I.F., Skau, C.F.: Ordered Bratteli diagrams, dimension groups and topological dynamics. Int. J. Math. 3, 827–864 (1992)MathSciNet CrossRef MATH
  33.Hochman, M.: On the dynamics and recursive properties of multidimensional symbolic systems. Inventiones Mathematicae 176, 131–167 (2009)MathSciNet CrossRef MATH
  34.Hochman, M., Meyerovitch, T.: A characterization of the entropies of multidimensional shifts of finite type. Ann. Math. 171, 2011–2038 (2010)MathSciNet CrossRef MATH
  35.Galatolo, S., Hoyrup, M., Rojas, C.: Effective symbolic dynamics, random points, statistical behavior, complexity and entropy. Inf. Comput. 208, 23–41 (2010)MathSciNet CrossRef MATH
  36.Le, T.Q.T.: Local rules for quasiperiodic tilings. In: The Mathematics of Long-Range Aperiodic Order, Waterloo, ON, 1995. NATO Advanced Science Institutes Series C: Mathematical and Physical Sciences, vol. 489, pp. 331–366. Kluwer Academic Publisher, Dordrecht (1997)
  37.Levitov, L.S.: Local rules for quasicrystals. Commun. Math. Phys. 119, 627–666 (1988)MathSciNet CrossRef
  38.Mozes, S.: Tilings, substitution systems and dynamical systems generated by them. J. d’analyse mathématique 53, 139–186 (1989)MathSciNet CrossRef MATH
  39.Priebe, N.M.: Towards a characterization of self-similar tilings in terms of derived Vorono tessellations. Geom. Dedicata. 79, 239–265 (2000)MathSciNet CrossRef MATH
  40.Robinson, R.M.: Undecidability and nonperiodicity for tilings of the plane. Invent. Math. 12, 177–209 (1971)MathSciNet CrossRef MATH
  41.Rigo, M.: Formal Languages, Automata and Numeration Systems. Wiley, Hoboken (2014)CrossRef MATH
  42.Shallit, J.: Decidability and enumeration for automatic sequences: a survey. In: Bulatov, A.A., Shur, A.M. (eds.) CSR 2013. LNCS, vol. 7913, pp. 49–63. Springer, Heidelberg (2013)CrossRef
  43.Socolar, J.E.S.: Weak matching rules for quasicrystals. Commun. Math. Phys. 129, 599–619 (1990)MathSciNet CrossRef MATH
  44.V’yugin, V.V.: Effective convergence in probability, and an ergodic theorem for individual random sequences. Theor. Probab. Appl. 42, 42–50 (1997)MathSciNet MATH
  
• 作者单位：Valérie Berthé (16)
  Thomas Fernique (17)
  Mathieu Sablik (18)
  
  16. IRIF, CNRS UMR 8243, Univ. Paris Diderot, Paris, France
  17. LIPN, CNRS UMR 7030, Univ. Paris 13, Villetaneuse, France
  18. I2M UMR 7373, Aix Marseille Univ., Marseille, France
  
• 丛书名：Pursuit of the Universal
• ISBN：978-3-319-40189-8
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9709

文摘

We focus in this survey on effectiveness issues for S-adic subshifts and tilings. An S-adic subshift or tiling space is a dynamical system obtained by iterating an infinite composition of substitutions, where a substitution is a rule that replaces a letter by a word (that might be multi-dimensional), or a tile by a finite union of tiles. Several notions of effectiveness exist concerning S-adic subshifts and tiling spaces, such as the computability of the sequence of iterated substitutions, or the effectiveness of the language. We compare these notions and discuss effectiveness issues concerning classical properties of the associated subshifts and tiling spaces, such as the computability of shift-invariant measures and the existence of local rules (soficity). We also focus on planar tilings.