Expand, Enlarge and Check: New algorithms for the coverability problem of WSTS

摘要

In this paper, we present a general algorithmic schema called ‘Expand, Enlarge and Check’ from which new algorithms for the coverability problem of WSTS can be constructed. We show here that our schema allows us to define forward algorithms that decide the coverability problem for several classes of systems for which the Karp and Miller procedure cannot be generalized, and for which no complete forward algorithms were known. Our results have important applications for the verification of parameterized systems and communication protocols.A preliminary version of this paper has been published as [Geeraerts et al., Expand, enlarge and check: new algorithms for the coverability problem of WSTS, in: Proceedings of the 24th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 04), Lecture Notes in Computer Science, vol. 3328, Springer, Berlin, 2004, pp. 287–298] in the proceedings of FST&TCS 2004.