View in EDS

Regional controllability of cellular automata as a SAT problem.

Saved in:
Bibliographic Details
Title: Regional controllability of cellular automata as a SAT problem.
Authors: Bagnoli, Franco1,2 (AUTHOR) franco.bagnoli@unifi.it, Dridi, Sara3 (AUTHOR) sara.dridi@univ-setif.dz, Fatès, Nazim4 (AUTHOR) nazim.fates@loria.fr
Source: Natural Computing. 2026, Vol. 25 Issue 1, p1-16. 16p.
Subjects: Cellular automata, Satisfiability (Computer science), System analysis, System dynamics, Controllability in systems engineering
Abstract: 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. [ABSTRACT FROM AUTHOR]
Copyright of Natural Computing is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 190671691
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Regional controllability of cellular automata as a SAT problem.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Bagnoli%2C+Franco%22">Bagnoli, Franco</searchLink><relatesTo>1,2</relatesTo> (AUTHOR)<i> franco.bagnoli@unifi.it</i><br /><searchLink fieldCode="AR" term="%22Dridi%2C+Sara%22">Dridi, Sara</searchLink><relatesTo>3</relatesTo> (AUTHOR)<i> sara.dridi@univ-setif.dz</i><br /><searchLink fieldCode="AR" term="%22Fatès%2C+Nazim%22">Fatès, Nazim</searchLink><relatesTo>4</relatesTo> (AUTHOR)<i> nazim.fates@loria.fr</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Natural+Computing%22">Natural Computing</searchLink>. 2026, Vol. 25 Issue 1, p1-16. 16p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Cellular+automata%22">Cellular automata</searchLink><br /><searchLink fieldCode="DE" term="%22Satisfiability+%28Computer+science%29%22">Satisfiability (Computer science)</searchLink><br /><searchLink fieldCode="DE" term="%22System+analysis%22">System analysis</searchLink><br /><searchLink fieldCode="DE" term="%22System+dynamics%22">System dynamics</searchLink><br /><searchLink fieldCode="DE" term="%22Controllability+in+systems+engineering%22">Controllability in systems engineering</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Natural Computing is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=190671691
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s11047-025-10061-6
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 16
        StartPage: 1
    Subjects:
      – SubjectFull: Cellular automata
        Type: general
      – SubjectFull: Satisfiability (Computer science)
        Type: general
      – SubjectFull: System analysis
        Type: general
      – SubjectFull: System dynamics
        Type: general
      – SubjectFull: Controllability in systems engineering
        Type: general
    Titles:
      – TitleFull: Regional controllability of cellular automata as a SAT problem.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Bagnoli, Franco
      – PersonEntity:
          Name:
            NameFull: Dridi, Sara
      – PersonEntity:
          Name:
            NameFull: Fatès, Nazim
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 03
              Text: 2026
              Type: published
              Y: 2026
          Identifiers:
            – Type: issn-print
              Value: 15677818
          Numbering:
            – Type: volume
              Value: 25
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: Natural Computing
              Type: main
ResultId 1