TY - GEN
T1 - Bounds on non-surjective cellular automata
AU - Kari, Jarkko
AU - Vanier, Pascal
AU - Zeume, Thomas
PY - 2009/9/28
Y1 - 2009/9/28
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/70349312637
U2 - 10.1007/978-3-642-03816-7_38
DO - 10.1007/978-3-642-03816-7_38
M3 - Conference contribution
AN - SCOPUS:70349312637
SN - 3642038158
SN - 9783642038150
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 439
EP - 450
BT - Mathematical Foundations of Computer Science 2009 - 34th International Symposium, MFCS 2009, Proceedings
T2 - 34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009
Y2 - 24 August 2009 through 28 August 2009
ER -