Abstraction model checking
Encyclopedia
Abstraction Model checking is for systems where an actual representation is too complex in developing the model alone. So, the design undergoes a kind of translation to scaled down "abstract" version.
The set of variables
are partitioned into visible and invisible depending on their change of values. The real state space
is summarized into a smaller set of the visible ones.
. This means that if we take an element from the abstract space
, concretize it and abstract the concretized version, the result will be equal to the original. On the other hand, if you pick an element from the real space, abstract it and concretize the abstract version, the final result will be a super set of the original.
That is,
(
(abstract)) = abstract
(
(real)) 
real
is that although the abstraction simulates the real, when the abstraction does not satisfy a property, it does not mean that this property actually fails in the real model. Counter examples are checked against the real state space because we obtain "spurious" counter examples. So a part of the abstraction refinement loop is:
Spurious examples are mostly generated because dead end states and bad states are abstracted to the same kind. To solve this we need to create a segregation between the 2 kinds. The next step is to find the subset of invisible variables that actually make a difference between the dead end and bad states and add this subset to the set of visible or monitored variables. If the separation proves expensive, refinement could be based on learning from samples.
The set of variables
Variable (mathematics)
In mathematics, a variable is a value that may change within the scope of a given problem or set of operations. In contrast, a constant is a value that remains unchanged, though often unknown or undetermined. The concepts of constants and variables are fundamental to many areas of mathematics and...
are partitioned into visible and invisible depending on their change of values. The real state space
State space
In the theory of discrete dynamical systems, a state space is a directed graph where each possible state of a dynamical system is represented by a vertex, and there is a directed edge from a to b if and only if ƒ = b where the function f defines the dynamical system.State spaces are...
is summarized into a smaller set of the visible ones.
Galois connected
The real and the abstract state spaces are Galois connectedGalois connection
In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets . The same notion can also be defined on preordered sets or classes; this article presents the common case of posets. Galois connections generalize the correspondence...
. This means that if we take an element from the abstract space
Abstract space
Abstract space, in geography, refers to a hypothetical space characterized by equal and consistent properties; a geographic space that is completely homogeneous. All movement and activity would be equally easy or difficult in all directions and all locations within this space...
, concretize it and abstract the concretized version, the result will be equal to the original. On the other hand, if you pick an element from the real space, abstract it and concretize the abstract version, the final result will be a super set of the original.
That is,
((abstract)) = abstract ((real)) realAbstraction refinement loop
A problem with abstraction model checkingModel checking
In computer science, model checking refers to the following problem:Given a model of a system, test automatically whether this model meets a given specification....
is that although the abstraction simulates the real, when the abstraction does not satisfy a property, it does not mean that this property actually fails in the real model. Counter examples are checked against the real state space because we obtain "spurious" counter examples. So a part of the abstraction refinement loop is:
- Obtain the abstract model
- Model check and see if everything is ok.
- If there is a counter example, then go back to the real state space and find out if it actually a counter model.
- If not, return and continue model checking.
Spurious examples are mostly generated because dead end states and bad states are abstracted to the same kind. To solve this we need to create a segregation between the 2 kinds. The next step is to find the subset of invisible variables that actually make a difference between the dead end and bad states and add this subset to the set of visible or monitored variables. If the separation proves expensive, refinement could be based on learning from samples.