Cellular automata and powers of p∕q
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Special issue dedicated to the 16th "Journées Montoises d’Informatique Théorique", Tome 51 (2017) no. 4, pp. 191-204.

We consider one-dimensional cellular automata Fp,q which multiply numbers by p∕q in base pq for relatively prime integers p and q. By studying the structure of traces with respect to Fp,q we show that for p≥2q-1 (and then as a simple corollary for p>q>1) there are arbitrarily small finite unions of intervals which contain the fractional parts of the sequence ξ(p∕q)n,(n=0,1,2,...), for some ξ>0. To the other direction, by studying the measure theoretical properties of , Fp,q, we show that for p>q>1 there are finite unions of intervals approximating the unit interval arbitrarily well wich don't contain the fractional parts of the whole sequence ξ(p/q)n for any ξ>0.

DOI : 10.1051/ita/2017014
Classification : 11J71, 37A25, 68Q80
Mots-clés : Distribution modulo 1, Z-numbers, cellular automata, ergodicity, strongly mixing
Kari, Jarkko 1 ; Kopra, Johan 1

1 
@article{ITA_2017__51_4_191_0,
     author = {Kari, Jarkko and Kopra, Johan},
     title = {Cellular automata and powers of p\ensuremath{/}q},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {191--204},
     publisher = {EDP-Sciences},
     volume = {51},
     number = {4},
     year = {2017},
     doi = {10.1051/ita/2017014},
     mrnumber = {3782820},
     zbl = {1432.11081},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2017014/}
}
TY  - JOUR
AU  - Kari, Jarkko
AU  - Kopra, Johan
TI  - Cellular automata and powers of p∕q
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2017
SP  - 191
EP  - 204
VL  - 51
IS  - 4
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2017014/
DO  - 10.1051/ita/2017014
LA  - en
ID  - ITA_2017__51_4_191_0
ER  - 
%0 Journal Article
%A Kari, Jarkko
%A Kopra, Johan
%T Cellular automata and powers of p∕q
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2017
%P 191-204
%V 51
%N 4
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita/2017014/
%R 10.1051/ita/2017014
%G en
%F ITA_2017__51_4_191_0
Kari, Jarkko; Kopra, Johan. Cellular automata and powers of p∕q. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Special issue dedicated to the 16th "Journées Montoises d’Informatique Théorique", Tome 51 (2017) no. 4, pp. 191-204. doi : 10.1051/ita/2017014. https://www.numdam.org/articles/10.1051/ita/2017014/

[1] S. Akiyama, Mahler’s Z-number and 3/2 number system. Unif. Distrib. Theory 3 (2008) 91–99. | MR | Zbl

[2] S. Akiyama, Ch. Frougny and J. Sakarovitch, Powers of rationals modulo 1 and rational base number systems. Isr. J. Math. 168 (2008) 53–91. | DOI | MR | Zbl

[3] A. Dubickas, On the powers of 3/2 and other rational numbers. Math. Nachr. 281 (2008) 951–958. | DOI | MR | Zbl

[4] L. Flatto, J.C. Lagarias and A.D. Pollington, On the range of fractional parts {ξ(p∕q)n }. Acta Arith. 70 (1995) 125–147. | DOI | MR | Zbl

[5] G. Hedlund, Endomorphisms and automorphisms of shift dynamical systems. Math. Syst. Theory 3 (1969) 320–375. | DOI | MR | Zbl

[6] J. Kari, Cellular automata, the Collatz conjecture and powers of 3/2, in Developments in Language Theory. Vol. 7410 of Lecture Notes in Computer Science (2012) 40–49. | DOI | MR | Zbl

[7] J. Kari, Universal pattern generation by cellular automata. Theor. Comput. Sci. 429 (2012) 180–184. | DOI | MR | Zbl

[8] K. Mahler, An unsolved problem on the powers of 3/2. J. Aust. Math. Soc. 8 (1968) 313–321. | DOI | MR | Zbl

[9] W. Rudin, Real and Complex Analysis. McGraw-Hill Book Company, New York (1966). | MR | Zbl

[10] P. Walters, An Introduction to Ergodic Theory. Springer-Verlag, New York (1982). | DOI | MR

[11] H. Weyl, Über die Gleichverteilung von Zahlen mod. Eins. Math. Ann. 77 (1916) 313–352. | DOI | JFM | MR

  • Kopra, Johan Rapid left expansivity, a commonality between Wolfram's Rule 30 and powers of p/q, Theoretical Computer Science, Volume 946 (2023), p. 113668 | DOI:10.1016/j.tcs.2022.12.018
  • Kopra, Johan On the Interplay of Direct Topological Factorizations and Cellular Automata Dynamics on Beta-Shifts, International Journal of Foundations of Computer Science, Volume 32 (2021) no. 06, p. 663 | DOI:10.1142/s012905412142003x
  • Kopra, Johan On computing the Lyapunov exponents of reversible cellular automata, Natural Computing, Volume 20 (2021) no. 2, p. 273 | DOI:10.1007/s11047-020-09821-3
  • Kopra, Johan On the trace subshifts of fractional multiplication automata, Theoretical Computer Science, Volume 851 (2021), p. 92 | DOI:10.1016/j.tcs.2020.11.010
  • Aman, Bogdan; Ciobanu, Gabriel; Glück, Robert; Kaarsgaard, Robin; Kari, Jarkko; Kutrib, Martin; Lanese, Ivan; Mezzina, Claudio Antares; Mikulski, Łukasz; Nagarajan, Rajagopal; Phillips, Iain; Pinna, G. Michele; Prigioniero, Luca; Ulidowski, Irek; Vidal, Germán Foundations of Reversible Computation, Reversible Computation: Extending Horizons of Computing, Volume 12070 (2020), p. 1 | DOI:10.1007/978-3-030-47361-7_1

Cité par 5 documents. Sources : Crossref