Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Verifying Systems of Resource-Bounded Agents Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Effective S-adic Symbolic Dynamical Systems

verfasst von : Valérie Berthé, Thomas Fernique, Mathieu Sablik

Erschienen in: Pursuit of the Universal

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Verifying Systems of Resource-Bounded Agents
Nächstes Kapitel Reaction-Based Models of Biochemical Networks
Literatur
1.
Arnoux, P., Ito, S.: Pisot substitutions and Rauzy fractals. Bull. Belg. Math. Soc. Simon Stevin 8, 181–207 (2001)MathSciNetMATH
2.
Aubrun, N., Sablik, M.: Multidimensional effective S-adic systems are sofic. Distrib. Theor. 9, 7–29 (2014)MathSciNetMATH
3.
Aubrun, N., Sablik, M.: Simulation of effective subshifts by two-dimensional subshifts of finite type. Acta Applicandae Mathematicae 126, 35–63 (2013)MathSciNetCrossRefMATH
4.
Baake, M., Grimm, U.: Aperiodic Order: A Mathematical Invitation, vol. 1. Cambridge University Press, Cambridge (2013)CrossRefMATH
5.
6.
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)MathSciNetCrossRefMATH
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)MathSciNetCrossRefMATH
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)MathSciNetCrossRefMATH
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)MathSciNetCrossRefMATH
17.
Charlier, E., Rampersad, N., Shallit, J.: Enumeration and decidable properties of automatic sequences. Int. J. Found. Comput. Sci. 23, 1035–1066 (2012)MathSciNetCrossRefMATH
18.
de Bruijn, N.G.: Algebraic theory of Penrose’s nonperiodic tilings of the plane. Nederl. Akad. Wetensch. Indag. Math. 43, 39–66 (1981)MathSciNetCrossRefMATH
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)MathSciNetMATH
22.
23.
24.
Durand, F., Host, B., Skau, C.: Substitutional dynamical systems, Bratteli diagrams and dimension groups. Ergodic Theor. Dyn. Syst. 19(4), 953–993 (1999)MathSciNetCrossRefMATH
25.
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.
29.
30.
31.
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)MathSciNetCrossRefMATH
33.
Hochman, M.: On the dynamics and recursive properties of multidimensional symbolic systems. Inventiones Mathematicae 176, 131–167 (2009)MathSciNetCrossRefMATH
34.
Hochman, M., Meyerovitch, T.: A characterization of the entropies of multidimensional shifts of finite type. Ann. Math. 171, 2011–2038 (2010)MathSciNetCrossRefMATH
35.
Galatolo, S., Hoyrup, M., Rojas, C.: Effective symbolic dynamics, random points, statistical behavior, complexity and entropy. Inf. Comput. 208, 23–41 (2010)MathSciNetCrossRefMATH
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.
38.
Mozes, S.: Tilings, substitution systems and dynamical systems generated by them. J. d’analyse mathématique 53, 139–186 (1989)MathSciNetCrossRefMATH
39.
Priebe, N.M.: Towards a characterization of self-similar tilings in terms of derived Vorono tessellations. Geom. Dedicata. 79, 239–265 (2000)MathSciNetCrossRefMATH
40.
41.
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.
44.
V’yugin, V.V.: Effective convergence in probability, and an ergodic theorem for individual random sequences. Theor. Probab. Appl. 42, 42–50 (1997)MathSciNetMATH
Metadaten
Titel
Effective S-adic Symbolic Dynamical Systems
verfasst von
Valérie Berthé
Thomas Fernique
Mathieu Sablik
Copyright-Jahr
2016
Buch
Pursuit of the Universal

Print ISBN: 978-3-319-40188-1

Electronic ISBN: 978-3-319-40189-8

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-40189-8_2