Abstract
One possible complexity measure for a cellular automaton is the size of its neighborhood. If a cellular automaton is reversible with a small neighborhood, the inverse automaton may need a much larger neighborhood. Our interest is to find good upper bounds for the size of this inverse neighborhood. It turns out that a linear algebra approach provides better bounds than any known combinatorial methods. We also consider cellular automata that are not surjective. In this case there must exist so-called orphans, finite patterns without a pre-image. The length of the shortest orphan measures the degree of non-surjectiveness of the map. Again, a linear algebra approach provides better bounds on this length than known combinatorial methods. We also use linear algebra to bound the minimum lengths of any diamond and any word with a non-balanced number of pre-images. These both exist when the cellular automaton in question is not surjective. All our results deal with one-dimensional cellular automata. Undecidability results imply that in higher dimensional cases no computable upper bound exists for any of the considered quantities.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Hedlund, G.: Endomorphisms and automorphisms of shift dynamical systems. Mathematical Systems Theory 3, 320–375 (1969)
Kari, J.: Reversibility and surjectivity problems of cellular automata. Journal of Computer and System Sciences 48, 149–182 (1994)
Kari, J.: Theory of Cellular Automata: a survey. Theoretical Computer Science 334, 3–33 (2005)
Czeizler, E., Kari, J.: A tight linear bound on the neighborhood of inverse cellular automata. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 410–420. Springer, Heidelberg (2005)
Kari, J., Vanier, P., Zeume, T.: Bounds on non-surjective cellular automata. In: Královič, R., Niwiński, D. (eds.) MFCS 2009. LNCS, vol. 5734, pp. 439–450. Springer, Heidelberg (2009)
Moore, E.F.: Machine Models of Self-reproduction. In: Proceedings of the Symposium in Applied Mathematics, vol. 14, pp. 17–33 (1962)
Myhill, J.: The Converse to Moore’s Garden-of-Eden Theorem. Proceedings of the American Mathematical Society, 14, 685–686 (1963)
Sutner, K.: De Bruijn Graphs and Linear Cellular Automata. Complex Systems 5, 19–30 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kari, J. (2011). Linear Algebra Based Bounds for One-Dimensional Cellular Automata. In: Holzer, M., Kutrib, M., Pighizzini, G. (eds) Descriptional Complexity of Formal Systems. DCFS 2011. Lecture Notes in Computer Science, vol 6808. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22600-7_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-22600-7_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22599-4
Online ISBN: 978-3-642-22600-7
eBook Packages: Computer ScienceComputer Science (R0)