{"id":"arxiv/2606.30270","url":"https://arxiv.org/abs/2606.30270","tags":["cs.CC","cs.DM","math.DS"],"score":0,"title":"A Complete Complexity Dichotomy for Cyclic Attractor Detection in Boolean Networks with Restricted Local Rules","domain":"cs.CC","source":"arxiv","authors":["Alexander Drobyshev","Grigoriy Bokov"],"reviews":0,"subject":"cs.CC","summary":"Boolean networks (BNs) are finite models of interacting systems whose long-term behaviour is organised by attractors. After a transient phase, every synchronously updated BN reaches either a fixed state or a cyclic attractor. Therefore, deciding whether a prescribed cyclic behaviour exists is a basic computational task in finite-state network dynamics. Here we study this task for networks with restricted local rules: each node is updated by a Boolean rule from a fixed closed rule family, and the period is fixed in advance. We prove a complete dichotomy for every fixed period at least two.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-29","reactions":{}}