{"ID":2892801,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.14569","arxiv_id":"2507.14569","title":"Characterizing and Testing Configuration Stability in Two-Dimensional Threshold Cellular Automata","abstract":"We consider the problems of characterizing and testing the stability of cellular automata configurations that evolve on a two-dimensional torus according to threshold rules with respect to the von-Neumann neighborhood. While stable configurations for Threshold-1 (OR) and Threshold-5 (AND) are trivial (and hence easily testable), the other threshold rules exhibit much more diverse behaviors. We first characterize the structure of stable configurations with respect to the Threshold-2 (similarly, Threshold-4) and Threshold-3 (Majority) rules. We then design and analyze a testing algorithm that distinguishes between configurations that are stable with respect to the Threshold-2 rule, and those that are $ε$-far from any stable configuration, where the query complexity of the algorithm is independent of the size of the configuration and depends quadratically on $1/ε$.","short_abstract":"We consider the problems of characterizing and testing the stability of cellular automata configurations that evolve on a two-dimensional torus according to threshold rules with respect to the von-Neumann neighborhood. While stable configurations for Threshold-1 (OR) and Threshold-5 (AND) are trivial (and hence easily...","url_abs":"https://arxiv.org/abs/2507.14569","url_pdf":"https://arxiv.org/pdf/2507.14569v1","authors":"[\"Yonatan Nakar\",\"Dana Ron\"]","published":"2025-07-19T10:35:28Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}