Lossless State Compression of Boolean Control Networks
Bowen Li, Jianquan Lu, Wenying Xu, Jie Zhong
Abstract
In this paper, the problem of lossless state compression of Boolean control networks (BCNs) is firstly investigated. Two compression protocols are introduced, based on which an inequality relation between the smallest compressed state walk and a source state walk is established to search all the eligible compressed state walks. Then, by defining indistinguishable trajectories and utilizing the semi-tensor product approach, some matrix-based conditions for the solvability of lossless state compression are derived. In order to reduce constraints, the finite state automaton method is proposed to obtain more applicable solvability conditions. Furthermore, in order to improve compression ratio, one algorithm is given to construct the minimal recoverable compressed state walk. Finally, some examples are given to illustrate the efficiency of the derived results, in which the compression ratio can reach 33.3%.