Electronic Notes in Theoretical Computer Science · 2001 · 79 citations · 9 references
ComputingComputer ScienceAlgorithmsFormal MethodsTheory Of ComputationAutomata TheoryModel CheckingModel TheoryRegular LanguagesParameterized Model CheckingSafety PropertiesSymbolic Model CheckingSymbolic VerificationTransitive Closure
In this paper, we consider symbolic model checking of safety properties of linear parametrized systems. Sets of configurations are represented by regular languages and actions by regular relations. Since the verification problem amounts to the computation of the reachability set, we focus on the computation of R∗(φ) for a regular relation R and a regular language φ. We present a technique called regular widening that allows, when it terminates, the computation of either the reachability set R∗(φ) of a system or the transitive closure R∗ of a regular relation. We show that our method can be uniformly applied to several parametrized systems. Furthermore, we show that it is powerful enough to simulate some existing methods that compute either R∗ or R∗(φ) for each R (resp. φ) belonging to a subclass of regular relations (resp. belonging to a subclass of regular languages).
9
On the verification of broadcast protocols
Javier Esparza, Alain Finkel, Richard Mayr · 2003 · 247 citations
E. Allen Emerson, Kedar S. Namjoshi · 1995 · 218 citations · Full text
Static determination of dynamic properties of recursive procedures
Patrick Cousot, Radhia Cousot · 1977 · 178 citations