Synchronous Boolean finite dynamical systems on directed graphs over XOR functions

DOI10.1007/s00224-022-10111-xMaRDI QIDQ6109069

Kei Uchizawa, Ogihara, Mitsunori

Publication date: 26 July 2023

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12754/

zbMATH Keywords

dynamical systemscycle lengthcomplexity classesGarden of Edenpath intersectioncompuational compleitypreducessorreachabilty

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of reachability problems for finite discrete dynamical systems
• Dichotomy results for fixed-point existence problems for Boolean dynamical systems
• Reachability problems for sequential dynamical systems with threshold functions.
• Elements of a theory of simulation. II: Sequential dynamical systems.
• Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs
• Dichotomy results for fixed point counting in Boolean dynamical systems
• Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs
• Predecessor existence problems for finite discrete dynamical systems

This page was built for publication: Synchronous Boolean finite dynamical systems on directed graphs over XOR functions