Geodesic
Automaticity and Invariant Measures of Linear Cellular Automata
Canadian journal of mathematics, Tome 72 (2020) no. 6, pp. 1691-1726

Voir la notice de l'article provenant de la source Cambridge University Press

We show that spacetime diagrams of linear cellular automata $\unicode[STIX]{x1D6F7}:\,\mathbb{F}_{p}^{\mathbb{Z}}\rightarrow \mathbb{F}_{p}^{\mathbb{Z}}$with $(-p)$-automatic initial conditions are automatic. This extends existing results on initial conditions that are eventually constant. Each automatic spacetime diagram defines a $(\unicode[STIX]{x1D70E},\unicode[STIX]{x1D6F7})$-invariant subset of $\mathbb{F}_{p}^{\mathbb{Z}}$, where $\unicode[STIX]{x1D70E}$ is the left shift map, and if the initial condition is not eventually periodic, then this invariant set is nontrivial. For the Ledrappier cellular automaton we construct a family of nontrivial $(\unicode[STIX]{x1D70E},\unicode[STIX]{x1D6F7})$-invariant measures on $\mathbb{F}_{3}^{\mathbb{Z}}$. Finally, given a linear cellular automaton $\unicode[STIX]{x1D6F7}$, we construct a nontrivial $(\unicode[STIX]{x1D70E},\unicode[STIX]{x1D6F7})$-invariant measure on $\mathbb{F}_{p}^{\mathbb{Z}}$ for all but finitely many $p$.
DOI : 10.4153/S0008414X19000488
Mots-clés : linear cellular automata, invariant measure, automatic sequence, Christol’s theorem 
Rowland, Eric; Yassawi, Reem. Automaticity and Invariant Measures of Linear Cellular Automata. Canadian journal of mathematics, Tome 72 (2020) no. 6, pp. 1691-1726. doi: 10.4153/S0008414X19000488
@article{10_4153_S0008414X19000488,
     author = {Rowland, Eric and Yassawi, Reem},
     title = {Automaticity and {Invariant} {Measures} of {Linear} {Cellular} {Automata}},
     journal = {Canadian journal of mathematics},
     pages = {1691--1726},
     year = {2020},
     volume = {72},
     number = {6},
     doi = {10.4153/S0008414X19000488},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/S0008414X19000488/}
}
TY  - JOUR
AU  - Rowland, Eric
AU  - Yassawi, Reem
TI  - Automaticity and Invariant Measures of Linear Cellular Automata
JO  - Canadian journal of mathematics
PY  - 2020
SP  - 1691
EP  - 1726
VL  - 72
IS  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.4153/S0008414X19000488/
DO  - 10.4153/S0008414X19000488
ID  - 10_4153_S0008414X19000488
ER  - 
%0 Journal Article
%A Rowland, Eric
%A Yassawi, Reem
%T Automaticity and Invariant Measures of Linear Cellular Automata
%J Canadian journal of mathematics
%D 2020
%P 1691-1726
%V 72
%N 6
%U http://geodesic.mathdoc.fr/articles/10.4153/S0008414X19000488/
%R 10.4153/S0008414X19000488
%F 10_4153_S0008414X19000488

[1] Adamczewski, B. and Bell, J. P., Diagonalization and rationalization of algebraic Laurent series. Ann. Sci. Éc. Norm. Supér. (4) 46(2013), 963–1004. https://doi.org/10.24033/asens.2207 Google Scholar | DOI

[2] Allouche, J.-P. and Berthé, V., Triangle de Pascal, complexité et automates. Journées Montoises (Mons, 1994). Bull. Belg. Math. Soc. Simon Stevin 4(1997), 1–23. Google Scholar | DOI

[3] Allouche, J.-P., Deshouillers, J.-M., Kamae, T., and Koyanagi, T., Automata, algebraicity and distribution of sequences of powers. Ann. Inst. Fourier (Grenoble) 51(2001), 687–705. Google Scholar | DOI

[4] Allouche, J.-P. and Shallit, J., Automatic sequences: Theory, applications, generalizations. Cambridge University Press, Cambridge, 2003. https://doi.org/10.1017/CBO9780511546563 Google Scholar | DOI

[5] Allouche, J.-P., Von Haeseler, F., Lange, E., Petersen, A., and Skordev, G., Linear cellular automata and automatic sequences. Cellular automata (Gießen, 1996). Parallel Comput. 23(1997), 1577–1592. https://doi.org/10.1016/S0167-8191(97)00074-4 Google Scholar | DOI

[6] Allouche, J.-P., Von Haeseler, F., Peitgen, H.-O., Petersen, A., and Skordev, G., Automaticity of double sequences generated by one-dimensional linear cellular automata. Theoret. Comput. Sci. 188(1997), 195–209. https://doi.org/10.1016/S0304-3975(96)00298-8 Google Scholar | DOI

[7] Allouche, J.-P., Von Haeseler, F., Peitgen, H.-O., and Skordev, G., Linear cellular automata, finite automata and Pascal’s triangle. Discrete Appl. Math. 66(1996), 1–22. https://doi.org/10.1016/0166-218X(94)00132-W Google Scholar | DOI

[8] Aparicio Monforte, A. and Kauers, M., Formal Laurent series in several variables. Expo. Math. 31(2013), 350–367. https://doi.org/10.1016/j.exmath.2013.01.004 Google Scholar PubMed | DOI

[9] Arnoux, P. and Ito, S., Pisot substitutions and Rauzy fractals. Journées Montoises d’Informatique Théorique (Marne-la-Vallée, 2000), Bull. Belg. Math. Soc. Simon Stevin 8(2001), 181–207. Google Scholar | DOI

[10] Bartlett, A., Spectral theory of ℤd substitutions. Ergodic Theory Dynam. Systems 38(2018), 1289–1341. https://doi.org/10.1017/etds.2016.66 Google Scholar | DOI

[11] Berthé, V., Complexité et automates cellulaires linéaires. Theor. Inform. Appl. 34(2000), 403–423. https://doi.org/10.1051/ita:2000124 Google Scholar | DOI

[12] Bezuglyi, S., Kwiatkowski, J., Medynets, K., and Solomyak, B., Invariant measures on stationary Bratteli diagrams. Ergodic Theory Dynam. Systems 30(2010), 973–1007. https://doi.org/10.1017/S0143385709000443 Google Scholar | DOI

[13] Bousquet-Mélou, M. and Petkov̌Sek, M., Linear recurrences with constant coefficients: the multivariate case. Formal power series and algebraic combinatorics (Toronto, ON, 1998). Discrete Math. 225(2000), 51–75. https://doi.org/10.1016/S0012-365X(00)00147-3 Google Scholar | DOI

[14] Boyle, M., Open problems in symbolic dynamics. In: Geometric and probabilistic structures in dynamics. Contemp. Math., 469, Amer. Math. Soc., Providence, RI, 2008, pp. 69–118. https://doi.org/10.1090/conm/469/09161 Google Scholar | DOI

[15] Charlier, E., Rampersad, N., and Shallit, J., Enumeration and decidable properties of automatic sequences. Internat. J. Found. Comput. Sci. 23(2012), 1035–1066. https://doi.org/10.1142/S0129054112400448 Google Scholar | DOI

[16] Christol, G., Ensembles presque periodiques k-reconnaissables. Theoret. Comput. Sci. 9(1979), 141–145. https://doi.org/10.1016/0304-3975(79)90011-2 Google Scholar | DOI

[17] Christol, G., Kamae, T., Mendès France, M., and Rauzy, G., Suites algébriques, automates et substitutions. Bull. Soc. Math. France 108(1980), 401–419. Google Scholar | DOI

[18] Cobham, A., Uniform tag sequences. Math. Systems Theory 6(1972), 164–192. https://doi.org/10.1007/BF01706087 Google Scholar | DOI

[19] Cyr, V. and Kra, B., Nonexpansive ℤ2-subdynamics and Nivat’s conjecture. Trans. Amer. Math. Soc. 367(2015), 6487–6537. https://doi.org/10.1090/S0002-9947-2015-06391-0 Google Scholar | DOI

[20] Cyr, V. and Kra, B., Free ergodic ℤ2-systems and complexity. Proc. Amer. Math. Soc. 145(2017), 1163–1173. https://doi.org/10.1090/proc/13279 Google Scholar | DOI

[21] Einsiedler, M., Invariant subsets and invariant measures for irreducible actions on zero-dimensional groups. Bull. London Math. Soc. 36(2004), 321–331. https://doi.org/10.1112/S0024609303003023 Google Scholar | DOI

[22] Furstenberg, H., Disjointness in ergodic theory, minimal sets, and a problem in Diophantine approximation. Math. Systems Theory 1(1967), 1–49. https://doi.org/10.1007/BF01692494 Google Scholar | DOI

[23] Host, B., Maass, A., and Martínez, S., Uniform Bernoulli measure in dynamics of permutative cellular automata with algebraic local rules. Discrete Contin. Dyn. Syst. 9(2003), 1423–1446. https://doi.org/10.3934/dcds.2003.9.1423 Google Scholar | DOI

[24] Kari, J. and Moutot, E., Nivat’s conjecture and pattern complexity in algebraic subshifts. Theoret. Comput. Sci. 777(2019), 379–386. https://doi.org/10.1016/j.tcs.2018.12.029 Google Scholar | DOI

[25] Kitchens, B. and Schmidt, K., Markov subgroups of (/2)Z2. In: Symbolic dynamics and its applications (New Haven, CT, 1991), Contemp. Math., 135, Amer. Math. Soc., Providence, RI, 1992, pp. 265–283. https://doi.org/10.1090/conm/135/1185094 Google Scholar | DOI

[26] Massuir, A., Peltomäki, J., and Rigo, M., Automatic sequences based on Parry or Bertrand numeration systems. Adv. in Appl. Math. 108(2019), 11–30. https://doi.org/10.1016/j.aam.2019.03.003 Google Scholar | DOI

[27] Mossé, B., Puissances de mots et reconnaissabilité des points fixes d’une substitution. Theoret. Comput. Sci. 99(1992), 327–334. https://doi.org/10.1016/0304-3975(92)90357-L Google Scholar | DOI

[28] Mousavi, H., Automatic theorem proving in Walnut. Google Scholar

[29] Pivato, M., Ergodic theory of cellular automata. In: Computational complexity. Vols. 1–6. Springer, New York, 2012, pp. 965–999. https://doi.org/10.1007/978-1-4614-1800-9_62 Google Scholar | DOI

[30] Pivato, M. and Yassawi, R., Limit measures for affine cellular automata. Ergodic Theory Dynam. Systems 22(2002), 1269–1287. https://doi.org/10.1017/S0143385702000548 Google Scholar | DOI

[31] Pivato, M. and Yassawi, R., The spatial structure of odometers in cellular automata. JAC 2008 (2009), 119–129. Google Scholar

[32] Quas, A. and Zamboni, L., Periodicity and local complexity. Theoret. Comput. Sci. 319(2004), 229–240. https://doi.org/10.1016/j.tcs.2004.02.026 Google Scholar | DOI

[33] Rigo, M., Formal languages, automata and numeration systems. 2. Applications to recognizability and decidability. Networks and Telecommunications Series. ISTE, London, John Wiley & Sons, Inc., Hoboken, NJ, 2014. Google Scholar

[34] Rowland, E., IntegerSequences. Google Scholar

[35] Rowland, E. and Yassawi, R., A characterization of p-automatic sequences as columns of linear cellular automata. Adv. in Appl. Math. 63(2015), 68–89. https://doi.org/10.1016/j.aam.2014.10.002 Google Scholar | DOI

[36] Salon, O., Suites automatiques à multi-indices et algébricité. C. R. Acad. Sci. Paris Sér. I Math. 305(1987), 501–504. Google Scholar

[37] Schmidt, K., Dynamical systems of algebraic origin. Progress in Mathematics, 128, Birkha̋user Verlag, Basel, 1995. Google Scholar

[38] Silberger, S., Subshifts of the three dot system. Ergodic Theory Dynam. Systems 25(2005), 1673–1687. https://doi.org/10.1017/S0143385705000015 Google Scholar | DOI

[39] Walters, P., An introduction to ergodic theory. Graduate Texts in Mathematics, 79, Springer-Verlag, New York, Berlin, 1982. Google Scholar | DOI

Cité par Sources :