Document Open Access Logo

Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions

Authors Mitsunori Ogihara, Kei Uchizawa

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2020.76.pdf
  • Filesize: 450 kB
  • 13 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
Keywords
  • Computational complexity
  • dynamical systems
  • Garden of Eden
  • predecessor
  • reachability

Metrics

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.

Cite As Get BibTex

Mitsunori Ogihara and Kei Uchizawa. Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 76:1-76:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.MFCS.2020.76

Author Details

Mitsunori Ogihara
  • Department of Computer Science, University of Miami, FL, USA
Kei Uchizawa
  • Graduate School of Science and Engineering, Yamagata University, Japan

Funding

This work was supported by JSPS KAKENHI Grant Numbers JP19K11817.

Acknowledgements

We thank the reviewers for their constructive criticisms and many valuable suggestions.

References

  1. C. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz, and R. E. Stearns. Reachability problems for sequential dynamical systems with threshold functions. Theoretical Computer Science, 295(1-3):41-64, 2003. Google Scholar
  2. C. L. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz, and R. E. Stearns. Complexity of reachability problems for finite discrete dynamical systems. Journal of Computer and System Sciences, 72(8):1317-1345, 2006. Google Scholar
  3. C. L. Barrett, H. B. Hunt III, M. V. Marathe, D. J. Rosenkrantz S. S. Ravi, R. E. Stearns, and M. Thakur. Predecessor existence problems for finite discrete dynamical systems. Theoretical Computer Science, 386(1-2):3-37, 2007. Google Scholar
  4. C. L. Barrett, H. B.Hunt III, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz, and R. E. Stearns. Predecessor and permutation existence problems for sequential dynamical systems. In Proceedings of Discrete Mathematics and Theoretical Computer Science, pages 69-80, 2003. Google Scholar
  5. C. L. Barrett, H. B.Hunt III, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz, R. E. Stearns, and P. T. Tosic. Gardens of eden and fixed points in sequential dynamical systems. In Proceedings of Discrete Mathematics and Theoretical Computer Science, pages 95-110, 2001. Google Scholar
  6. C. L. Barrett, H. S. Mortveit, and C. M. Reidys. Elements of a theory of simulation II: Sequential dynamical systems. Applied Mathematics and Computation, 107(2-3):121-136, 2000. Google Scholar
  7. G. H. Hardy and E. M. Wrigth. An Introduction to the Theory of Numbers. 6th edition. In R. Heath-brown et al. (Eds.). Oxford University Press, 2008. Google Scholar
  8. A. Kawachi. Personal communication, 2016. Google Scholar
  9. A. Kawachi, M. Ogihara, and K. Uchizawa. Generalized predecessor existence problems for boolean finite dynamical systems on directed graphs. Theoretical Computer Science, 762:25-40, 2019. Google Scholar
  10. S. Kosub. Dichotomy results for fixed-point existence problems for boolean dynamical systems. Mathematics in Computer Science, 1(3):487-505, 2008. Google Scholar
  11. S. Kosub and C. M. Homan. Dichotomy results for fixed point counting in boolean dynamical systems. In Proceedings of the Tenth Italian Conference on Theoretical Computer Science, pages 163-174, 2007. Google Scholar
  12. M. Ogihara and K. Uchizawa. Computational complexity studies of synchronous boolean finite dynamical systems on directed graphs. Information and Computation, 256:226-236, 2017. Google Scholar
  13. D. J. Rosenkrantz, M. V. Marathe, H. B. Hunt III, S. S. Ravi, and R. E. Stearns. Analysis problems for graphical dynamical systems: A unified approach through graph predicates. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, pages 1501-1509, 2015. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact