A P systems variant for reasoning about sequential controllability of Boolean networks
Închide
Conţinutul numărului revistei
Articolul precedent
Articolul urmator
162 0
SM ISO690:2012
ALHAZOV, Artiom, FERRARI-DOMINGUEZ, Vincent, FREUND, Rudolf, GLADE, Nicolas, IVANOV, Sergiu. A P systems variant for reasoning about sequential controllability of Boolean networks. In: Theoretical Computer Science, 2023, vol. 970, pp. 1-29. ISSN 0304-3975. DOI: https://doi.org/10.1016/j.tcs.2023.114056
EXPORT metadate:
Google Scholar
Crossref
CERIF

DataCite
Dublin Core
Theoretical Computer Science
Volumul 970 / 2023 / ISSN 0304-3975 /ISSNe 1879-2294

A P systems variant for reasoning about sequential controllability of Boolean networks

DOI:https://doi.org/10.1016/j.tcs.2023.114056

Pag. 1-29

Alhazov Artiom1, Ferrari-Dominguez Vincent2, Freund Rudolf3, Glade Nicolas4, Ivanov Sergiu5
 
1 Vladimir Andrunachievici Institute of Mathematics and Computer Science,
2 Ecole Normale Superieure, Paris,
3 Vienna University of Technology,
4 Grenoble Alpes University,
5 Universitatea Paris-Saclay
 
 
Disponibil în IBN: 24 iulie 2023


Rezumat

A Boolean network is a discrete dynamical system operating on vectors of Boolean variables. The action of a Boolean network can be conveniently expressed as a system of Boolean update functions, computing the new values for each component of the Boolean vector as a function of the other components. Boolean networks are widely used in modeling biological systems that can be seen as consisting of entities which can be activated or deactivated, expressed or inhibited, on or off. P systems on the other hand are classically introduced as a model of hierarchical multiset rewriting. However, over the years the community has proposed a wide range of P system variants including diverse ingredients suited for various needs. In this work, we propose a new variant—Boolean P systems—specifically designed for reasoning about sequential controllability of Boolean networks, and use it to first establish a crisp formalization of the problem, and then to prove that the problem of sequential controllability is PSPACE-complete. We further claim that Boolean P systems are a demonstration of how P systems can be used to construct ad hoc formalisms, custom-tailored for reasoning about specific problems, and providing new advantageous points of view. 

Cuvinte-cheie
Boolean networks, Boolean P systems, complexity, reachability