Computer Science – Logic in Computer Science
Scientific paper
2004-01-21
Computer Science
Logic in Computer Science
Scientific paper
Standard abstract model checking relies on abstract Kripke structures which approximate concrete models by gluing together indistinguishable states, namely by a partition of the concrete state space. Strong preservation for a specification language L encodes the equivalence of concrete and abstract model checking of formulas in L. We show how abstract interpretation can be used to design abstract models that are more general than abstract Kripke structures. Accordingly, strong preservation is generalized to abstract interpretation-based models and precisely related to the concept of completeness in abstract interpretation. The problem of minimally refining an abstract model in order to make it strongly preserving for some language L can be formulated as a minimal domain refinement in abstract interpretation in order to get completeness w.r.t. the logical/temporal operators of L. It turns out that this refined strongly preserving abstract model always exists and can be characterized as a greatest fixed point. As a consequence, some well-known behavioural equivalences, like bisimulation, simulation and stuttering, and their corresponding partition refinement algorithms can be elegantly characterized in abstract interpretation as completeness properties and refinements.
Ranzato Francesco
Tapparo Francesco
No associations
LandOfFree
Generalized Strong Preservation by Abstract Interpretation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Generalized Strong Preservation by Abstract Interpretation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generalized Strong Preservation by Abstract Interpretation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-641471