Improving the Effectiveness of SAT Approach in Application to Analysis of Several Discrete Models of Collective Behavior

摘要

In this paper we study several discrete models of collective behavior based on Synchronous Boolean Networks. For these models we consider a number of related problems that we solve by reducing them to Boolean satisfiability problem (SAT) and applying state-of-the-art parameterized SAT solving algorithms. We describe a greedy algorithm that exploits the features of functions used to recalculate network nodes weights and interconnections between neighborhoods of network nodes. This algorithm in combination with several specific propositional encoding techniques, makes it possible to significantly reduce the size of propositional encoding. We compare the effectiveness of SAT solving algorithms on the new encodings with that on previously employed encodings and evaluate the total performance gain achieved by using state-of-the-art tools for finding efficient SAT solver parameters.