Computational Complexity Studies of Synchronous Boolean Finite Dynamical Systems
A finite dynamical system is a system consisting of some finite number of objects that take upon a value from some domain as a state, in which after initialization the states of the objects are updated based upon the states of the other objects and themselves according to a certain update schedule.
-
Convergence. Does a system at hand converge on a given initial state configuration?
-
Path Intersection. Will a system starting in given two state configurations produce a common configuration?
-
Cycle Length. Since the state space is finite, every BFDS on a given initial state configuration either converges or enters a cycle having length greater than 1. If the latter is the case, what is the length of the loop? Or put more simply, for an integer tt, is the length of loop greater than tt?
Read More . . .
Ogihara, M., & Uchizawa, K. (2015). Computational complexity studies of synchronous boolean finite dynamical systems. In Theory and Applications of Models of Computation – 12th Annual Conference, TAMC 2015, Proceedings (Vol. 9076, pp. 87-98). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9076). Springer Verlag. DOI: 10.1007/978-3-319-17142-5_9