2026-07-25T01:58:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8107 2024-03-06T10:40:49Z ddc:004 open_access

Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems Kawachi, Akinori Ogihara, Mitsunori Uchizawa, Kei Computational complexity dynamical systems Garden of Eden predecessor A Boolean Finite Synchronous Dynamical System (BFDS, for short) consists of a finite number of objects that each maintains a boolean state, where after individually receiving state assignments, the objects update their state with respect to object-specific time-independent boolean functions synchronously in discrete time steps. The present paper studies the computational complexity of determining, given a boolean finite synchronous dynamical system, a configuration, which is a boolean vector representing the states of the objects, and a positive integer t, whether there exists another configuration from which the given configuration can be reached in t steps. It was previously shown that this problem, which we call the t-Predecessor Problem, is NP-complete even for t = 1 if the update function of an object is either the conjunction of arbitrary fan-in or the disjunction of arbitrary fan-in. This paper studies the computational complexity of the t-Predecessor Problem for a variety of sets of permissible update functions as well as for polynomially bounded t. It also studies the t-Garden-Of-Eden Problem, a variant of the t-Predecessor Problem that asks whether a configuration has a t-predecessor, which itself has no predecessor. The paper obtains complexity theoretical characterizations of all but one of these problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Akinori Kawachi and Mitsunori Ogihara and Kei Uchizawa 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.8 urn:nbn:de:0030-drops-81078 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.8 eng https://creativecommons.org/licenses/by/3.0/legalcode