Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

One‑dimensional cellular automata can be analyzed through their translation into edge‑labeled deBruijn graphs, where configurations and their images correspond to bi‑infinite paths. This viewpoint turns the question of whether a given periodic configuration lies in the image of the global transition function into a question about cycles with prescribed labels. I will discuss the probability that a given periodic configuration appears as an image when the local update rule is chosen uniformly at random. Two complementary asymptotic regimes emerge: fixed neighborhood size with growing state space, and fixed state space with growing neighborhood size. The talk will highlight how tools such as the Chen–Stein method for Poisson approximation, aperiodic necklace enumeration, and structural properties of deBruijn graphs combine to describe the image space of a random cellular automaton.