Is Lazy Abstraction a Decision Procedure for Broadcast Protocols?
Rayna Dimitrova and Andreas Podelski
Lazy abstraction builds up an abstract reachability tree by locally refining abstractions in order to eliminate spurious counterexamples in smaller and smaller subtrees. The method has proven useful to verify systems code. It is still open how good the method is as a decision procedure, i.e., whether the method terminates for already known decidable verification problems. In this paper, we answer the question positively for broadcast protocols and other infinite-state models in the class of so-called well-structured systems. This extends an existing result on systems with a finite bisimulation quotient.
9th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI 2008).