×

Bounds on non-surjective cellular automata. (English) Zbl 1250.68205

Královič, Rastislav (ed.) et al., Mathematical foundations of computer science 2009. 34th international symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24–28, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03815-0/pbk). Lecture Notes in Computer Science 5734, 439-450 (2009).
Summary: Cellular automata (CA) are discrete, homogeneous dynamical systems. Non-surjective one-dimensional CA have finite words with no preimage (called orphans), pairs of different words starting and ending identically and having the same image (diamonds) and words with more/fewer preimages than the average number (unbalanced words). Using a linear algebra approach, we obtain new upper bounds on the lengths of the shortest such objects. In the case of an \(n\)-state, non-surjective CA with neighborhood range 2 our bounds are of the orders \(O(n ^{2})\), \(O(n ^{3/2})\) and \(O(n)\) for the shortest orphan, diamond and unbalanced word, respectively.
For the entire collection see [Zbl 1173.68012].

MSC:

68Q80 Cellular automata (computational aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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) · Zbl 1082.68072 · doi:10.1007/11523468_34
[2] Hedlund, G.: Endomorphisms and automorphisms of shift dynamical systems. In: Mathematical Systems Theory, vol. 3, pp. 320–375. Springer, Heidelberg (1969) · Zbl 0182.56901
[3] Kari, J.: Reversibility and surjectivity problems of cellular automata. J. Comput. Syst. Sci. 48, 149–182 (1994) · Zbl 0802.68090 · doi:10.1016/S0022-0000(05)80025-X
[4] Kari, J.: Synchronizing finite automata on eulerian digraphs. Theor. Comput. Sci. 295(1-3), 223–232 (2003) · Zbl 1045.68082 · doi:10.1016/S0304-3975(02)00405-X
[5] Moore, E.F.: Machine models of self reproduction. In: Mathematical Society Proceedings of Symposia in Applied Mathematics, vol. 14, pp. 17–33 (1962) · Zbl 0126.32408 · doi:10.1090/psapm/014/9961
[6] Subrahmonian Moothathu, T.K.: Studies in Topological Dynamics with Emphasis on Cellular Automata. PhD thesis, Department of Mathematics and Statistics, School of MCIS, University of Hyderabad (2006) · Zbl 1087.68063
[7] Myhill, J.: The converse of Moore’s garden-of-eden theorem. Proc. Amer. Math. Soc. 14, 685–686 (1963) · Zbl 0126.32501
[8] Pin, J.-E.: Utilisation de l’algèbre linéaire en théorie des automates. In: Actes du 1er Colloque AFCET-SMF de Mathématiques Appliquées, pp. 85–92. AFCET (1978)
[9] Sutner, K.: Linear cellular automata and de bruijn automata. In: Mathematics and Its Applications 4, vol. 460, pp. 303–320. Kluwer, Dordrecht (1999)
[10] Toffoli, T., Capobianco, S., Mentrasti, P.: When–and how–can a cellular automaton be rewritten as a lattice gas? Theor. Comput. Sci. 403, 71–88 (2008) · Zbl 1155.68052 · doi:10.1016/j.tcs.2008.04.047
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.