2024-03-30T00:44:14Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001423032024-03-29T05:26:34Z01164:02592:07834:08269
Computational Complexity Studies of Synchronous Boolean Finite Dynamical SystemsComputational Complexity Studies of Synchronous Boolean Finite Dynamical Systemsenghttp://id.nii.ac.jp/1001/00142239/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=142303&item_no=1&attribute_id=1&file_no=1Copyright (c) 2015 by the Information Processing Society of JapanDepartment of Computer Science, University of MiamiFaculty of Engineering, Yamagata UniversityMitsunori, OgiharaKei, UchizawaThis paper studies the subclass of finite dynamical systems the synchronous boolean finite dynamical system (synchronous BFDS, for short), where the states are boolean and the state update takes place in discrete time and at the same on all objects. The present paper is concerned with some problems regarding the behavior of synchronous BFDS in which the state update functions (or the local state transition functions) are chosen from a predetermined finite basis of boolean functions B. Specifically the following three behaviors are studied: (1) Does a system at hand converge on a given initial state configuration? (2) Will a system starting in given two state configurations produce a common configuration? (3) 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? We prove that the three problems are each PSPACE-complete if the boolean function basis contains NAND, NOR or both AND and OR, while the problem (1) is in P, the problem (2) is in UP, and the problem (3) is in UP ∩ coUP if the set B is one of {AND}, {OR} and {XOR, NXOR}.This paper studies the subclass of finite dynamical systems the synchronous boolean finite dynamical system (synchronous BFDS, for short), where the states are boolean and the state update takes place in discrete time and at the same on all objects. The present paper is concerned with some problems regarding the behavior of synchronous BFDS in which the state update functions (or the local state transition functions) are chosen from a predetermined finite basis of boolean functions B. Specifically the following three behaviors are studied: (1) Does a system at hand converge on a given initial state configuration? (2) Will a system starting in given two state configurations produce a common configuration? (3) 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? We prove that the three problems are each PSPACE-complete if the boolean function basis contains NAND, NOR or both AND and OR, while the problem (1) is in P, the problem (2) is in UP, and the problem (3) is in UP ∩ coUP if the set B is one of {AND}, {OR} and {XOR, NXOR}.AN1009593X研究報告アルゴリズム(AL)2015-AL-1533162015-06-052188-85662015-05-28