An Algorithmic Framework for Coverability in Well-Structured Systems
Tim Strazny, Roland Meyer · 2012
We generalize the backward algorithm for cover ability in WSTS's to an algorithmic framework. The idea is to consider the predecessor computation, the witness function, and the processing order as parameters. On the theoretical side, we prove that every instantiation of the functions (that satisfies some requirements) still yields a decision procedure for cover ability. On the practical side, we show that known optimizations like partial order reduction and pruning can be formulated in our framework. We also give a novel acceleration based instantiation. For well-known classes of WSTS's (PN, PN+Transfer, LCS), we optimize the selection function inspired by A*. We implemented our instantiations and comment on the data structures. Extensive experiments show that the new algorithms can compete with a state-of-the-art tool: MIST2.