Trap spaces as labelled ideals of SCC posets: A structural-functional theory of reachability in asynchronous boolean...

Boolean networks provide a qualitative framework for modelling regulatory systems when kinetic parameters are unavailable, with cellular phenotypes represented as attractors of the induced dynamics [J. D. Schwab et al., Concepts in Boolean network modeling, Comput. Struct. Biotechnol. J. 18:571-582, 2020]. A central challenge is phenotypic reachability: determining whether asynchronous dynamics can connect invariant regions of the state space, a problem that becomes computationally intractable in large networks [L. Cifuentes-Fontanals, M. Noual, and E. Remy, Revisiting trap spaces in Boolean networks, Theor. Comput. Sci. 915:1-20, 2022; K. Perrot and C. Paulevé, Complexity of asynchronous reachability in Boolean networks, Theor. Comput. Sci. 1000:114650, 2024.]. We develop a structural theory of reachability in which trap spaces are identified with labelled order ideals of SCC-posets. The SCC-poset determines the order of commitment events, while admissible evaluations encode branching within regulatory modules, so that multistability appears as an intrinsic feature of the theory. Within this framework, we establish necessary and sufficient conditions for reachability, introduce the commitment depth, and show that deciding non-trivial branching is computationally intractable. We further demonstrate that effective interaction structure is jointly determined by topology and Boolean logic. We validate the framework on a Boolean model of CD4[Formula: see text] T-cell differentiation, where refinement chains recover the observed ordering of cytokine response, lineage commitment, and phenotypic branching. In the absence of multistability the structure collapses to a distributive lattice, a non-generic limiting regime.