Preprint 2024-23
Julio Aracena, Luis Cabrera-Crot, Adrien Richard, Lilian Salinas:
Dynamically equivalent disjunctive networks
Abstract:
The study of the dynamical behavior of Boolean networks with different update schedules has so far focused primarily on the possible dynamics and equivalent networks that can be obtained. However, few studies have been done about which networks can be obtained from another network with a non-parallel schedule. In this article, we define the problem of finding a Boolean network that is dynamically equivalent to another network. For the general case, it is shown that the problem is NP- Hard. However, if the problem is restricted to disjunctive Boolean networks, it can be solved in polynomial time.
This preprint gave rise to the following definitive publication(s):
Julio ARACENA, Luis CABRERA-CROT, Adrien RICHARD, Lilian SALINAS: Dynamically equivalent disjunctive networks. Theoretical Computer Science, vol. 1024, Paper No. 114899, (2025).