On Finite Covering of Infinite Spaces for Protocol Test Selection

The core of the protocol test selection problem lies in how to derive a finite test suite from an infinite set of possible execution sequences (protocol behaviors). This paper presents two promising approaches to this problem : (i) the metric based topological approach, and (ii) the formal language theoretic approach ; both aim at producing finite coverings of an infinite set of execution sequences. The former approach makes use of the property of compactness of metric space, which guarantees the infinite metric space can be fully covered by a finite number of open "balls" (subspaces). The latter approach relies on the property that the Parikh mapping of a set of all execution sequences can be represented by a finite union of linear sets. Two simple protocol examples are given to elucidate the formal language theoretic approach.