Regional Controllability of Cellular Automata as a SAT Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913777650237440 |
|---|---|
| author | Bagnoli, Franco Dridi, Sara Fates, Nazim |
| author_facet | Bagnoli, Franco Dridi, Sara Fates, Nazim |
| contents | Controllability, one of the fundamental concepts in control theory, consists in guiding a system from an initial state to a desired one within a limited (and possibly minimum) time interval. When the objective is limited to a specific sub-region of the system's domain, the concept is referred to as regional controllability. We examine this notion in the context of Boolean one-dimensional cellular automata of finite length. Depending on the local evolution rule, we investigate whether it is possible to control the evolution of the system by imposing particular values on the boundary conditions. This approach is related to key dynamical properties of CA, specifically chain transitivity and chain mixing. We show that the control problem can be formulated as a Boolean satisfiability (SAT) problem and can thus be addressed using SAT solvers. We also show how finding shortest paths in the configuration graph allows to determine controllability properties. From our observations we can state that only peripherally-linear rules are fully controllable, while for other rules, the reachability ratio, that is, the fraction of controllable pairs of initial and final configurations, is vanishing when the system size grows. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_03691 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Regional Controllability of Cellular Automata as a SAT Problem Bagnoli, Franco Dridi, Sara Fates, Nazim Cellular Automata and Lattice Gases Controllability, one of the fundamental concepts in control theory, consists in guiding a system from an initial state to a desired one within a limited (and possibly minimum) time interval. When the objective is limited to a specific sub-region of the system's domain, the concept is referred to as regional controllability. We examine this notion in the context of Boolean one-dimensional cellular automata of finite length. Depending on the local evolution rule, we investigate whether it is possible to control the evolution of the system by imposing particular values on the boundary conditions. This approach is related to key dynamical properties of CA, specifically chain transitivity and chain mixing. We show that the control problem can be formulated as a Boolean satisfiability (SAT) problem and can thus be addressed using SAT solvers. We also show how finding shortest paths in the configuration graph allows to determine controllability properties. From our observations we can state that only peripherally-linear rules are fully controllable, while for other rules, the reachability ratio, that is, the fraction of controllable pairs of initial and final configurations, is vanishing when the system size grows. |
| title | Regional Controllability of Cellular Automata as a SAT Problem |
| topic | Cellular Automata and Lattice Gases |
| url | https://arxiv.org/abs/2504.03691 |