Ogihara, Mitsunori ;
Uchizawa, Kei
Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions
Abstract
In this paper, we investigate the complexity of a number of computational problems defined on a synchronous boolean finite dynamical system, where update functions are chosen from a template set of exclusiveor and its negation. We first show that the reachability and pathintersection problems are solvable in logarithmic spaceuniform AC¹ if the objects execute permutations, while the reachability problem is known to be in P and the pathintersection problem to be in UP in general. We also explore the case where the reachability or intersection are tested on a subset of objects, and show that this hardens complexity of the problems: both problems become NPcomplete, and even Π^p₂complete if we further require universality of the intersection. We next consider the exact cycle length problem, that is, determining whether there exists an initial configuration that yields a cycle in the configuration space having exactly a given length, and show that this problem is NPcomplete. Lastly, we consider the tpredecessor and tGarden of Eden problem, and prove that these are solvable in polynomial time even if the value of t is also given in binary as part of instance, and the two problems are in logarithmic spaceuniform NC² if the value of t is given in unary as part of instance.
BibTeX  Entry
@InProceedings{ogihara_et_al:LIPIcs:2020:12754,
author = {Mitsunori Ogihara and Kei Uchizawa},
title = {{Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {76:176:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771597},
ISSN = {18688969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12754},
URN = {urn:nbn:de:0030drops127543},
doi = {10.4230/LIPIcs.MFCS.2020.76},
annote = {Keywords: Computational complexity, dynamical systems, Garden of Eden, predecessor, reachability}
}
18.08.2020
Keywords: 

Computational complexity, dynamical systems, Garden of Eden, predecessor, reachability 
Seminar: 

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Issue date: 

2020 
Date of publication: 

18.08.2020 