Abstract
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 objectspecific timeindependent 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 tPredecessor Problem, is NPcomplete even for t = 1
if the update function of an object is either the conjunction of
arbitrary fanin or the disjunction of arbitrary fanin.
This paper studies the computational complexity of the tPredecessor Problem for a variety of sets of permissible update functions as well as for polynomially bounded t. It also studies the tGardenOfEden Problem, a variant of the tPredecessor Problem that asks whether a configuration has a tpredecessor, which itself has no predecessor. The paper obtains complexity theoretical characterizations of all but one of these problems.
BibTeX  Entry
@InProceedings{kawachi_et_al:LIPIcs:2017:8107,
author = {Akinori Kawachi and Mitsunori Ogihara and Kei Uchizawa},
title = {{Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {8:18:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770460},
ISSN = {18688969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and JeanFrancois Raskin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8107},
URN = {urn:nbn:de:0030drops81078},
doi = {10.4230/LIPIcs.MFCS.2017.8},
annote = {Keywords: Computational complexity, dynamical systems, Garden of Eden, predecessor}
}
Keywords: 

Computational complexity, dynamical systems, Garden of Eden, predecessor 
Collection: 

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) 
Issue Date: 

2017 
Date of publication: 

01.12.2017 