HAL CCSD
On the Effects of Firing Memory in the Dynamics of Conjunctive Networks
Goles, Eric
Montealegre, Pedro
Ríos-Wilson, Martín
Facultad de Ingeniería y Ciencias [Santiago] ; Universidad Adolfo Ibáñez [Santiago]
Universidad de Chile = University of Chile [Santiago] (UCHILE)
International audience
Lecture Notes in Computer Science
25th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA)
Guadalajara, Mexico
Alonso Castillo-Ramirez
Pedro P. B. de Oliveira
Springer International Publishing
hal-02312604
https://inria.hal.science/hal-02312604
https://inria.hal.science/hal-02312604/document
https://inria.hal.science/hal-02312604/file/484947_1_En_1_Chapter.pdf
https://inria.hal.science/hal-02312604
25th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2019, Guadalajara, Mexico. pp.1-19, ⟨10.1007/978-3-030-20981-0_1⟩
DOI: 10.1007/978-3-030-20981-0_1
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-030-20981-0_1
en
Boolean network
Firing memory
Conjunctive networks
Prediction problem
PSPACE
[INFO]Computer Science [cs]
info:eu-repo/semantics/conferenceObject
Conference papers
Boolean networks are one of the most studied discrete models in the context of the study of gene expression. In order to define the dynamics associated to a Boolean network, there are several update schemes that range from parallel or synchronous to asynchronous. However, studying each possible dynamics defined by different update schemes might not be efficient. In this context, considering some type of temporal delay in the dynamics of Boolean networks emerges as an alternative approach. In this paper, we focus in studying the effect of a particular type of delay called firing memory in the dynamics of Boolean networks. Particularly, we focus in symmetric (non-directed) conjunctive networks and we show that there exist examples that exhibit attractors of non-polynomial period. In addition, we study the prediction problem consisting in determinate if some vertex will eventually change its state, given an initial condition. We prove that this problem is PSPACE-complete.
TC 1
WG 1.5
http://creativecommons.org/licenses/by/
2019-06-26
info:eu-repo/semantics/OpenAccess