Action Codes
share
We provide a new perspective on the problem how high-level state machine models with abstract actions can be related to low-level models in which these actions are refined by sequences of concrete actions. We describe the connection between high-level and low-level actions using action codes, a variation of the prefix codes known from coding theory. For each action code ℛ, we introduce a contraction operator α_ℛ that turns a low-level model M into a high-level model, and a refinement operator ϱ_ℛ that transforms a high-level model N into a low-level model. We establish a Galois connection ϱ_ℛ(N) ⊑ M ⇔ N ⊑α_ℛ(M), where ⊑ denotes the well-known simulation preorder. In practice, we typically want to obtain an overapproximation of model M. To this end, we also introduce a concretization operator γ_ℛ. This operator behaves like the refinement operator, but adds arbitrary behavior at intermediate points during a refinement. We establish a second Galois connection α_ℛ(M) ⊑ N ⇔ M ⊑γ_ℛ(N). We show how an action code may be used to construct an adaptor that translates between concrete and abstract inputs and outputs during learning and conformance testing of a black-box system. If M models a black-box system then α_ℛ(M) describes the behavior that can be observed by a tester/learner that interacts with this system via an adaptor derived from code ℛ. Whenever we have established that α_ℛ(M) implements (or conforms to) N, we may conclude that M implements (or conforms to) γ_ℛ (N).
READ FULL TEXT