An “almost dual” to Gottschalk’s conjecture. (English) Zbl 1369.68261
Cook, Matthew (ed.) et al., Cellular automata and discrete complex systems. 22nd IFIP WG 1.5 international workshop, AUTOMATA 2016, Zurich, Switzerland, June 15–17, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-39299-8/pbk; 978-3-319-39300-1/ebook). Lecture Notes in Computer Science 9664, 77-89 (2016).
This work focuses on so-called post-surjectivity that complements the notion of pre-injectivity, where the latter in the setting of cellular automata means that two configurations differing only in finitely many points have equal image only if they are equal. Essentially, the authors of this work prove that both properties together imply reversibility, after which it is shown – for sofic groups only – post-surjectivity implies pre-injectivity, which ultimately gives rise to the conjecture that every post-surjective CA is pre-injective.
My overall impression is somehow that this is a niche topic, and for that reason more examples would help to fully appreciate the paper.
For the entire collection see [Zbl 1339.68006].
My overall impression is somehow that this is a niche topic, and for that reason more examples would help to fully appreciate the paper.
For the entire collection see [Zbl 1339.68006].
Reviewer: Jan Baetens (Gent)
MSC:
| 68Q80 | Cellular automata (computational aspects) |
References:
| [1] | Bartholdi, L.: Gardens of Eden and amenability on cellular automata. J. Eur. Math. Soc. 12(1), 241–248 (2010) · Zbl 1185.37020 · doi:10.4171/JEMS/196 |
| [2] | Capobianco, S.: On the induction operation for shift subspaces and cellular automata as presentations of dynamical systems. Inform. Comput. 207(11), 1169–1180 (2009) · Zbl 1192.68439 · doi:10.1016/j.ic.2009.02.006 |
| [3] | Capobianco, S., Guillon, P., Kari, J.: Surjective cellular automata far from the Garden of Eden. Disc. Math. Theor. Comput. Sci. 15(3), 41–60 (2013) · Zbl 1285.68099 |
| [4] | Capobianco, S., Kari, J., Taati, S.: Post-surjectivity and balancedness of cellular automata over groups. In: Kari, J., Törmä, I., Szabados, M. (eds) 21st International Workshop on Cellular Automata and Discrete Complex Systems: Exploratory Papers of AUTOMATA 2015, Turku Centre for Computer Science, TUCS Lecture Notes, vol. 24, pp. 31–38 (2015) |
| [5] | Ceccherini-Silberstein, T., Coornaert, M.: Cellular Automata and Groups. Springer Monographs in Mathematics. Springer, Heidelberg (2010) · Zbl 1218.37004 · doi:10.1007/978-3-642-14034-1 |
| [6] | Ceccherini-Silberstein, T., Machì, A., Scarabotti, F.: Amenable groups and cellular automata. Ann. Inst. Fourier 49(2), 673–685 (1999) · Zbl 0920.43001 · doi:10.5802/aif.1686 |
| [7] | Fiorenzi, F.: Cellular automata and strongly irreducible shifts of finite type. Theor. Comput. Sci. 299, 477–493 (2003) · Zbl 1042.68077 · doi:10.1016/S0304-3975(02)00492-9 |
| [8] | Gottschalk, W.H.: Some general dynamical notions. In: Gottschalk, W. (ed.) Recent Advances in Topological Dynamics. Lecture Notes in Mathematics, vol. 318. Springer, Heidelberg (1973) |
| [9] | Gromov, M.: Endomorphisms of symbolic algebraic varieties. J. European Math. Soc. 1, 109–197 (1999) · Zbl 0998.14001 · doi:10.1007/PL00011162 |
| [10] | Kari, J.: Theory of cellular automata: a survey. Theor. Comp. Sci. 334, 3–33 (2005) · Zbl 1080.68070 · doi:10.1016/j.tcs.2004.11.021 |
| [11] | Kari, J., Taati, S.: Statistical mechanics of surjective cellular automata. J. Stat. Phys. 160(5), 1198–1243 (2015) · Zbl 1360.37044 · doi:10.1007/s10955-015-1281-2 |
| [12] | Lind, D., Marcus, B.: An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge (1995) · Zbl 1106.37301 · doi:10.1017/CBO9780511626302 |
| [13] | Weiss, B.: Sofic groups and dynamical systems. Sankhyā: Indian. J Stat. 62A(3), 350–359 (2000) · Zbl 1148.37302 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
