License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.76
URN: urn:nbn:de:0030-drops-127543
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12754/
Go to the corresponding LIPIcs Volume Portal


Ogihara, Mitsunori ; Uchizawa, Kei

Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions

pdf-format:
LIPIcs-MFCS-2020-76.pdf (0.4 MB)


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 exclusive-or and its negation. We first show that the reachability and path-intersection problems are solvable in logarithmic space-uniform AC¹ if the objects execute permutations, while the reachability problem is known to be in P and the path-intersection 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 NP-complete, 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 NP-complete. Lastly, we consider the t-predecessor and t-Garden 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 space-uniform 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:1--76:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Javier Esparza and Daniel Kr{\'a}ľ},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12754},
  URN =		{urn:nbn:de:0030-drops-127543},
  doi =		{10.4230/LIPIcs.MFCS.2020.76},
  annote =	{Keywords: Computational complexity, dynamical systems, Garden of Eden, predecessor, reachability}
}

Keywords: Computational complexity, dynamical systems, Garden of Eden, predecessor, reachability
Collection: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Issue Date: 2020
Date of publication: 18.08.2020


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI