TY - GEN
T1 - On the effects of firing memory in the dynamics of conjunctive networks
AU - Goles, Eric
AU - Montealegre, Pedro
AU - Ríos-Wilson, Martín
N1 - Publisher Copyright:
© IFIP International Federation for Information Processing 2019.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
KW - Boolean network
KW - Conjunctive networks
KW - Firing memory
KW - PSPACE
KW - Prediction problem
UR - https://www.scopus.com/pages/publications/85068210647
U2 - 10.1007/978-3-030-20981-0_1
DO - 10.1007/978-3-030-20981-0_1
M3 - Conference contribution
AN - SCOPUS:85068210647
SN - 9783030209803
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1
EP - 19
BT - Cellular Automata and Discrete Complex Systems - 25th IFIP WG 1.5 International Workshop, AUTOMATA 2019, Proceedings
A2 - Castillo-Ramirez, Alonso
A2 - de Oliveira, Pedro P.B.
PB - Springer Verlag
T2 - 25th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2019
Y2 - 26 June 2019 through 28 June 2019
ER -