EE Seminar: Testing Dynamic Environments: The Case of Threshold Cellular Automata
Electrical Engineering Systems Seminar
Speaker: Yonatan Nakar
Ph.D. student under the supervision of Prof. Dana Ron
Wednesday, 19th March 2025, at 15:00
Room 011, Kitot Building, Faculty of Engineering
Testing Dynamic Environments: The Case of Threshold Cellular Automata
Abstract
We explore property testing in the context of dynamic environments, focusing on threshold cellular automata. We begin by identifying a set of conditions on local rules applicable to elementary cellular automata, and introduce a meta-algorithm for testing evolution according to these rules. This meta-algorithm has query complexity O(1/ϵ4)
(where ϵ
is the algorithm's proximity parameter). The algorithm is also non-adaptive and has one-sided error. We establish that all threshold rules satisfy these conditions, rendering them efficiently testable.
We then shift to a broader family of one-dimensional cellular automata, where the next state of each cell is determined by inspecting all the cells within distance at most r
from that cell. In this setting, we focus on the majority rule and introduce the concept of cell stability. Our structural analysis reveals that, apart from fixed-point configurations of the form (0r+10*+ 1r+11*)*
, all other stable configurations manifest a periodic structure. These configurations are characterized by repeating patterns of length O(r2)
each. Capitalizing on this structural result, we develop a testing algorithm for the property of configuration stability. The testing algorithm has query complexity O(r2/ϵ)
, is non-adaptive and has one-sided error.
We then move to two-dimensional cellular automata, where we characterize the structure of stable configurations evolving on a two-dimensional torus according to all threshold rules.
While stable configurations for Threshold-1 (OR) and Threshold-5 (AND) have a trivial structure, for Threshold-2, 3 and 4, which exhibit more complex behaviors, the structure is more intricate, especially for Threshold-3, which corresponds to the majority rule.
For the Threshold-2 rule (and the equivalent Threshold-4), in addition to the structural characterization, we also develop a testing algorithm for the property of configuration stability.
The algorithm has query complexity O(1/ϵ2)
and has one-sided error.
Overall, this work introduces new property testing algorithms and structural characterizations of threshold cellular automata, enhancing the theoretical understanding of their structure as well as translating this new understanding into algorithmic applications.
We believe that this is a rich area of study and suggest a variety of open problems and natural research directions that may extend and expand our results.
השתתפות בסמינר תיתן קרדיט שמיעה = עפ"י רישום שם מלא + מספר ת.ז. בדף הנוכחות שיועבר באולם במהלך הסמינר
