Complete FSM Testing Using Strong Separability Robert M. Hierons, Mohammad Reza Mousavi Abstract Apartness is a concept developed in constructive mathematics, which has resurfaced as a powerful notion for separating states in the area of model learning and model-based testing. We identify some fundamental shortcomings of apartness in quantitative models, such as in hybrid and stochastic systems. We propose a closely-related alternative, called strong separability and show that using it to replace apartness addresses the identified shortcomings. We adapt a well-known complete model-based testing method, called the Harmonized State Identifiers (HSI) method, to adopt the proposed notion of strong separability. We prove that the adapted HSI method is complete. As far as we are aware, this is the first work to show how complete test suites can be generated for quantitative models such as those found in the development of cyber-physical systems. I Introduction Testing is an important part of the software development process but has traditionally been a largely manual process and so expensive and error-prone. This has led to significant interest in techniques that support systematic, automated test generation. Model-based testing (MBT) forms an important class of such techniques in which test generation is based on a formal model (or specification ) that defines the set of behaviours that a correct system under test (SUT) may have. There are many MBT techniques, with corresponding tools and evidence of effectiveness when applied to industrial systems (see, e.g., [ 4 , 10 , 12 , 18 , 20 , 25 , 32 ] ). We refer to survey papers for an overview of the field and its developments [ 13 , 16 , 21 , 26 ] . In order to formally reason about the effectiveness of an MBT technique, it is normal to assume a common semantic domain between the specification and the SUT; in other words, the SUT is assumed to behave like an unknown model M_{I} that can be expressed using the same formalism as the specification M [ 11 ] . Much of the MBT work has concerned state-based semantic domains: either labelled transition systems (LTSs) [ 25 ] or finite state machines (FSMs) [ 17 ] . Typically, the state-based models of the SUT are not produced by the developer/tester and are only hypothesised as the common semantic domain to ground the MBT approach on formal foundations. This paper aims to widen the applicability of FSM-based test techniques to a range of modern systems for which test generation is particularly challenging. Interest in FSM-based testing goes back to the seminal work of Moore in 1956 [ 22 ] , with Hennie introducing a test generation algorithm in 1964 [ 12 ] . The behaviour of an FSM is defined by transitions between states, with a transition having a corresponding input and output. FSM-based test generation techniques typically aim to find two types of faults: output faults (a transition produces the wrong output); and state-transfer faults (a transition takes the SUT to the wrong state). State-transfer faults can lead to the SUT having more states than the specification FSM. If there can only be output faults then it is sufficient to generate and execute tests that cover all transitions of the specification M . However, this approach is known to be insufficient in situations in which there might be state-transfer faults [ 17 ] . There are many FSM-based test generation techniques that aim to find state-transfer faults in addition to output faults [ 3 ] ; these techniques utilise input sequences that separate states 1 1 1 An input sequence \bar{x} separates two states s_{1} and s_{2} of M if the input of \bar{x} leads to different output sequences when applied in s_{1} and s_{2} . of the specification M in order to identify (or check ) states. Most FSM-based test generations concern specification FSMs that are minimal, deterministic, and completely-specified 2 2 2 These terms are formally defined in Section II . and we also consider such FSMs. Test generation methods for other classes of FSMs are seen as future work and are discussed further in the Conclusions. Of particular interest are test generation techniques that produce m -complete test suites: test suites that are guaranteed to determine correctness as long as the SUT behaves like an (unknown) FSM that has at most m states. Possibly the best known such test generation technique is the W-method [ 4 , 32 ] , which uses a characterising set to identify states (separate a state from all other states of the specification). A key benefit of using a characterising set is that every (minimal, completely-specified, and deterministic) FSM has a characterising set and such a set can be found in low-order polynomial time. Two other, more recent, FSM-based test generation techniques, the Wp-method [ 10 ] and HSI-method [ 18 ] , also use (prefixes of) sequences from a characterising set in order to identify states and return smaller m -complete test suites. Now consider what happens if we wish to test a system in which an output is drawn from a continuous domain and observations are noisy. This is characteristic of cyber-physical systems [ 15 ] and the conformance problem for such systems has been extensively researched [ 30 , 1 , 8 ] . This situation could occur, for example, in black-box testing of an autonomous system; the outputs from a control system may well be discrete but these outputs are not actually observed in testing. Instead, the tester uses sensors (e.g., radars and LIDARs) to observe the physical interaction of the autonomous system with its environment. In such situations, observations are imprecise and we should not require that the specification and SUT produce the same output when given an input sequence. Testing has to take into account this imprecision and might do this by defining a metric m between observations (trajectories) and using a threshold t to define when two observations should be considered to be similar [ 6 , 30 ] . Then two observations o_{1} and o_{2} are considered to be similar if m(o_{1},o_{2})\leq t and an observation o_{2} constitutes a failure if the expected observation o_{1} is such that m(o_{1},o_{2})>t . Separability is thus defined in terms of such a threshold being exceeded. We obtain a similar situation when checking conformance between a stochastic state-based specification model and its implementation [ 31 , 30 , 7 ] ; this is a practical problem, e.g., in the automotive domain and has been studied in the literature [ 5 , 23 ] . In a stochastic FSM specification, for each state and input pair, a transition defines a distribution over outputs. Testing with input sequence \bar{x} then involves applying \bar{x} multiple times, obtaining a sample of values, and using a statistical test to check whether, with a stated confidence, that this sample is consistent with the specified distribution [ 14 ] . Typically, the statistical test will involve applying a measure (a test statistic) and comparing this against a fixed value (threshold) that depends upon the required confidence. So, again, we are comparing a measure against a threshold. Note, however, that in this case there is the potential to reduce the threshold by increasing the number of times that a test (input) sequence is applied. We need to reconsider what we mean by correctness (conformance) in scenarios such as those sketched above. It no longer makes sense to require that, for each input sequence \bar{x} , the SUT and specification produce the same output sequence. Instead, we might require that the output sequence produced by the SUT (i.e., observed in testing) is sufficiently similar to that produced by the specification [ 30 , 1 , 8 ] . This leads to a different conformance relation and so the proofs of completeness, for current FSM-based test techniques, do not apply. In this paper we also show that the W, Wp, and HSI methods need not be complete when using such conformance relations. The aim of the work described in this paper is to generalise FSM-based test techniques to conformance relations such as those described above. One option might have been to adapt current FSM-based test techniques to a particular application domain. However, we aimed to produce a more general solution that can be applied across a range of application domains. We took as a starting point recent work by Vaandrager [ 27 ] that shows that it is possible to reason about the completeness of several FSM-based test techniques in terms of apartness . Apartness is a form of inequality used in constructive mathematics. Vaandrager [ 27 ] showed how the notion of apartness can be used in the generation of a m -complete test set. We found, however, that the notion of apartness is too strong for the scenario of interest in this paper (see Section III ). In this paper we weaken apartness in a way that allows us to reason about FSM-based testing when conformance is based on a metric m and threshold t . We start by specifying a notion of conformance defined in terms of a metric m and threshold, which is reminiscent of the work on metric bisimulation [ 31 , 30 , 7 ] and conformance testing [ 1 , 8 ] . We then define the notion of strongly separable, which is strictly weaker than apartness and stronger than separability, and discuss its relevance to the proposed conformance relation. We consider the case where the states of the specification FSM M are pairwise strongly separable. We give a sufficient condition for a test suite to be m -complete, defined in terms of strong separability. We adapt the HSI-method to the scenarios we consider and show that the above sufficient condition implies that this version of the HSI-method returns m -complete test suites. This completeness result extends to the W-method and the Wp-method. Note that these are exactly the FSM-based test generation techniques considered by Vaandrager [ 27 ] . To illustrate the concepts throughout the paper and their potential applicability, we use the following hybrid systems model. The same example can be extended to cover stochastic aspects, but for the sake of readability we decided to use a minimal running example. Fig. 1: Continuous Thermostat System Example 1 Consider a thermostat system that senses the temperatures and uses it to switch a heater on/off and control the room temperature. A diagrammatic representation of the thermostat behaviour is depicted in Figure 1 . The system starts off at time zero and the room temperature at 20 degree Celsius (in the discrete state Off) and the temperature decreases linearly with a first derivative -1. When the temperature reaches 19 degrees Celsius, the display can be updated through a “read” action (which outputs 19) and the heater is switched on through the action “switch”, which outputs “on”. The behaviour in the state labelled “On” is similar, with the main difference being that the temperature increases linearly with the first derivative equal to 1. Consider an implementation in which the initial condition and the guards differ by 0.5 degree. We will compare such an implementation (as well as another faulty one) against the specification based on a notion of conformance in the remainder of the paper. The idea is to use an approximate notion of conformance that allows for an error margin and yet, produce test-cases that are complete, i.e., test cases that will fail on any non-conforming implementation with at most m states. Consider, for example, a notion of conformance that has a threshold of 0.5 degrees Celsius for temperature differences (and no difference in the switching outputs) and thus, it accepts the implementation that differs only 0.5 degree Celsius in temperature with the specification in Figure 1 , while rejecting those with temperature differences that exceed the threshold or have incorrect switching behaviour. In the rest of this paper we show how complete test suites can be produced for this specification. The paper makes the following main contributions. • We show that there are scenarios (classes of system, with a corresponding definition of conformance) in which the notion of apartness is too strong; • We define the notion of strong separability and demonstrate that this is applicable in the identified scenarios; • We give a sufficient condition for a test suite to be m -complete and show that test suites produced by the well-known Harmonized State Identifiers (HSI) method (as well as similar ones such as the Wp and W-methods) satisfy this condition as long as the specification is an FSM in which the states are pairwise strongly separable and, for state identification, we use sequences that strongly separate states; and • We illustrate all concepts through our running example and use this to show that the W, Wp and HSI methods are not complete if we do not adapt them (ie if we use separability rather than strong separability). The paper is structured as follows. We start, in Section II , by providing preliminary definitions. In Section III we extend classical FSM concepts and definitions to the scenarios of interest. Within this we define separability and apartness and show that there are classes of system, including the Thermostat example, where separability is not an apartness relation. This leads to us defining the notion of strong separability. In Section IV we give a sufficient condition, defined in terms of strong separability, for a test suite to be m -complete, with a consequence being that the well-known W, Wp, and HSI methods return m -complete test suites for the notion of conformance and class of system considered if we base the choice of state identifiers on strong separability rather than separability. We also show that separability is insufficient for these test generation techniques: they can return test suites that are incomplete. Finally, in Section V , we draw conclusions and describe possible lines of future work. II Preliminaries In this section we define what we mean by a Finite State Machine and provide classical definitions. In the next section we adapt this to the context of interest where, for example, outputs may be drawn from a metric space. Definition 1 A Finite State Machine (FSM) M is defined by a tuple (S,s_{0},X,Y,\delta,\lambda) in which: S is the finite set of states; s_{0}\in S is the initial state; X is the finite input alphabet; Y is the output alphabet; \delta:S\times X\rightarrow S is the transition function; and \lambda:S\times X\rightarrow Y is the output function. The transition function and the output function are lifted inductively to sequences of inputs, by defining \delta(s_{i},\varepsilon)=s_{i} , \delta(s_{i},x^{\prime}.\bar{x})=\delta(\delta(s_{i},x^{\prime}),\bar{x}) and \lambda(s_{i},\varepsilon)=\varepsilon , \lambda(s_{i},x^{\prime}.\bar{x})=\lambda(s_{i},x^{\prime}).\lambda(\delta(s_{i},x^{\prime}),\bar{x}) , where \varepsilon is the empty sequence, x^{\prime}\in X , \bar{x}\in X^{*} . These FSMs are deterministic since for each state and input there is only one possible next state and output. In addition, the FSMs are completely-specified: \delta and \lambda are total functions. In this paper we restrict attention to deterministic and completely-specified FSMs, leaving other classes of FSM as a problem for future work. In order to reason about testing and test effectiveness, it is normal to assume that the SUT behaves like an unknown model that can be expressed in the same formalism [ 11 ] . Assumption 1 The behaviour of the SUT can be represented by an FSM M_{I}=(Q,q_{0},X,Y,\delta_{I},\lambda_{I}) with the same input and output alphabets as the specification FSM M . We don’t assume that the FSM M_{I} is known, only that there is some such M_{I} . Note that the Definition 1 relaxes the standard definition of an FSM, which requires that the output alphabet Y is finite. This may not seem to be an important point since the set of outputs that can be produced by M is finite since M is deterministic and has finitely many states and inputs. However, allowing Y to be infinite has an impact on the set of potential SUTs being tested, which becomes infinite (even if we bound the number of states), and so the set of possible faults. Fig. 2: Discretised Thermostat System: A Specification and Two Implementations Example 2 Consider our thermostat in Example 1 (Figure 1 ); assume that we would like to focus on the input/output behaviour and abstract from the internal continuous dynamics of the states. The FSM arising from the specification in Figure 1 is depicted in Figure 2 . The FSM (as well as the two implementations depicted in the same figure), have the set of input symbols \{r,s\} , representing reading the temperature and switching the heater, respectively. The output set is \mathbb{R}\cup\{on,off\} , i.e., the (uncountable) set of real numbers for temperature and the status values \mathit{on} and \mathit{off} . In our example, the relaxation to allow for infinite outputs is essential here to represent the infinite set of possible faulty implementations with deviating outputs, while a finite set of inputs would be sufficient to represent any discretisation of the passing of time. We use {\mathcal{F}} to denote the set of FSMs with input alphabet X and output alphabet Y . Further, given integer m we use {\mathcal{F}}^{m} to denote the set of FSMs with input alphabet X , output alphabet Y , and at most m states. As noted, since Y need not be finite, the set {\mathcal{F}}^{m} might be infinite. The following shows that if Y is finite then so is {\mathcal{F}}^{m} ; from {\mathcal{F}}^{m} being finite it is not difficult to show that there must be a finite m -complete test suite. Proposition 1 Let us suppose that M=(Q,q_{0},X,Y,\delta,\lambda) is an FSM and Y is finite. Given integer m , we have that {\mathcal{F}}^{m} is finite. Proof: First, observe that each FSM in {\mathcal{F}}^{m} can be seen as being defined by a directed graph that shows the transitions and a mapping from each edge of the directed graph to a corresponding input x\in X and output y\in Y pair. In the directed graph, each vertex has outdegree |I| and there are only finitely many such directed graphs. In addition, for each such directed graph there are finitely many mappings from edges to input/output pairs. The result therefore holds. ∎ There is a correspondence between FSMs and states of FSMs: if M is an FSM and s_{i} is a state of M then we can also see s_{i} as being an FSM: the FSM formed by making s_{i} the initial state of M . We can thus use {\mathcal{F}} to denote the set of possible states of the unknown FSM M_{I} that represents the SUT. In traditional FSM-based testing, testing typically involves applying an input sequence to the SUT and checking that the output sequence produced is that specified. We can formalise this in terms of separating states and FSMs; we use the term d-separate in this paper in order to distinguish between the classical notion and that required for the scenarios of interest (defined in the next section). Definition 2 Given FSM M and states s_{1},s_{2}\in S , an input sequence \bar{x} d-separates s_{1} and s_{2} if and only if \lambda(s_{1},\bar{x})\neq\lambda(s_{2},\bar{x}) . If \bar{x} d-separates s_{1} and s_{2} then we can write s_{1}\not\equiv_{\bar{x}}s_{2} and say that s_{1} and s_{2} are d-separable. If \bar{x} does not d-separate s_{1} and s_{2} then we write s_{1}\equiv_{\bar{x}}s_{2} . Similarly, given a set W of input sequence, we write s_{1}\not\equiv_{W}s_{2} if some input sequence in W d-separates s_{1} and s_{2} and otherwise we write s_{1}\equiv_{W}s_{2} . It is straightforward to see that \equiv_{\bar{x}} is an equivalence relation. In addition, it can be applied when comparing two FSMs M and M_{I} since one can define an FSM that is the disjoint union of M and M_{I} . We get a corresponding notion of conformance, used in traditional FSM-based testing, which we call d-conformance. Definition 3 Given FSMs M=(S,s_{0},X,Y,\delta,\lambda) and M_{I}=(Q,q_{0},X,Y,\delta_{I},\lambda_{I}) , we have that M_{I} d-conforms to M if and only if for all \bar{x}\in X^{*} we have that M_{I}\equiv_{\bar{x}}M . III Conformance, Apartness and Strong Separation In this section we start by explaining how the notions of separability and conformance can be naturally translated to a range of scenarios in which outputs could be drawn from a metric space. We then define strong separability. III-A Separability and Conformance In the scenarios of interest an output might, for example, be the speed of a vehicle as measured by a sensor, which is an estimate of the actual speed. An output in Y could also be a probability distribution; in testing we then apply a test case multiple times, observe a set of values drawn from an unknown distribution, and use statistical hypothesis testing techniques. In such situations, we need some way of comparing the observations made with the expected output and we formalise this as a similarity relation \sim on outputs. As previously explained, such a notion of similarity will typically be defined in terms of a metric m and a threshold t (below, we use the running example to illustrate this). Note that \sim normally will not be transitive and therefore need not be an equivalence relation. The following lifts \sim to output sequences in the natural way (we use \varepsilon to denote the empty sequence): Definition 4 Given similarity relation \sim on Y , y,y^{\prime}\in Y , and \bar{y},\bar{y}^{\prime}\in Y^{*} we have that: • \varepsilon\sim\varepsilon ; • y\bar{y}\sim y^{\prime}\bar{y}^{\prime} if and only if y\sim y^{\prime} and \bar{y}\sim\bar{y}^{\prime} ; We can define conformance in terms of \sim as follows. Definition 5 Given FSMs M=(S,s_{0},X,Y,\delta,\lambda) and M_{I}=(Q,q_{0},X,Y,\delta_{I},\lambda_{I}) , we define that M_{I} conforms to M if and only if for all \bar{x}\in X^{*} we have that \lambda(s_{0},\bar{x})\sim\lambda_{I}(q_{0},\bar{x}) . Example 3 Consider the FSMs given in Figure 2 ; we define the distance between real-valued outputs to be the absolute difference between them; the distance between \mathit{on} and \mathit{off} (as well as the distance between real numbers on one hand, and status values) is defined to be \infty . Define two outputs o,o^{\prime}\in\mathbb{R} to be \epsilon -conforming, denoted by t\sim_{\epsilon}t^{\prime} , when |o-o^{\prime}|\leq\epsilon . This leads to a natural notion of conformance, inspired by the hybrid conformance literature [ 1 ] , on FSMs. According to this notion of conformance, \mathit{Specification} \sim_{0.5} \mathit{Implementation}_{0} . This conformance relation holds, because for all input sequences, the difference between the respective outputs is bounded by 0.5 . Consider the specification \mathit{Specification} and implementation \mathit{Implementation}_{1} in Figure 2 . It does not hold that \mathit{Specification} \sim_{0.5} \mathit{Implementation}_{1} . In fact, \mathit{Implementation}_{1} does not \epsilon -conform to \mathit{Specification} for any value of \epsilon , witnessed by the output to the input sequence \mathit{s}.\mathit{s}.\mathit{s} , in which the difference between the last output in the two systems is \infty . We can also define the notion of separating two states for the scenario of interest in which Y need not be finite and there is a similarity relation on outputs. Definition 6 Given FSM M and states s_{1},s_{2}\in S , an input sequence \bar{x} separates s_{1} and s_{2} if and only if \lambda(s_{1},\bar{x})\not\sim\lambda(s_{2},\bar{x}) . If \bar{x} separates s_{1} and s_{2} then we can write s_{1}\not\approx_{\bar{x}}s_{2} . If \bar{x} does not separate s_{1} and s_{2} then we write s_{1}\approx_{\bar{x}}s_{2} . Similarly, given a set W of input sequences, we write s_{1}\not\approx_{W}s_{2} if there is a input sequence in W that separates s_{1} and s_{2} and otherwise we write s_{1}\approx_{W}s_{2} . Where the input sequence of interest is clear, we often use \not\approx and \approx , avoiding reference to the actual input sequences used to separate states. Conformance and separability are related. Proposition 2 Given FSMs M=(S,s_{0},X,Y,\delta,\lambda) and M_{I}=(Q,q_{0},X,Y,\delta_{I},\lambda_{I}) , M_{I} conforms to M if and only if no input sequence separates s_{0} and q_{0} . When two FSMs, M and M_{I} do not conform to each other, we denote this by M\not\approx M_{I} ; following Proposition 2 , this can only happen if there exists \bar{x}\in X^{*} such that the initial states of M and M_{I} are separated, which we denote by M\not\approx_{\bar{x}}M_{I} . Example 4 Consider again the FSMs given in Figure 2 and the notion of similarity \sim_{0.5} ; we have that the states \mathit{Off} in \mathit{Specification} and \mathit{Off}_{0} in \mathit{Implementation}_{0} are not separable by any input sequence and the two FSMs conform to each other with respect to \sim_{0.5} . However, \mathit{Specification} and \mathit{Implementation}_{1} do not conform to each other. The input sequence s.s.s separates the states \mathit{Off} and \mathit{Off}_{1} , because the former produces the output sequence \mathit{on} . \mathit{off} . \mathit{on} , while the later produces \mathit{on} . \mathit{off} . \mathit{off} and the two output sequences have a distance of \infty . In order to reason about test effectiveness, we will use the notion of the product machine defined by a specification FSM M and an unknown FSM M_{I} that models the SUT. Definition 7 Given FSMs M=(S,s_{0},X,Y,\delta,\lambda) and M_{I}=(Q,q_{0},X,Y,\delta_{I},\lambda_{I}) , the product machine P(M,M_{I}) is the FSM (S\times Q\cup\{e\},(s_{0},q_{0}),X,Y\cup\{err\},\delta_{P},\lambda_{P}) for e\notin S\times Q and err\notin Y such that for every state (s_{i},q_{i})\in S\times Q of P(M,M_{I}) and input x\in X we have that • If \lambda(s_{i},x)\sim\lambda_{I}(q_{i},x) then \delta_{P}((s_{i},q_{i}),x)=(\delta(s_{i},x),\delta_{I}(q_{i},x)) and \lambda_{P}((s_{i},q_{i}),x))=\lambda_{I}(q_{i},x) ; • else \delta_{P}((s_{i},q_{i}),x)=e and \lambda_{P}((s_{i},q_{i}),x))=err . Further, for all x\in X we have that \delta_{P}(e,x)=e and \lambda_{P}(e,x)=err . The following shows how the product machine relates to finding faults in testing. Proposition 3 Given FSMs M and M_{I} , an input sequence \bar{x} separates M and M_{I} if and only if \bar{x} takes the product machine P(M,M_{I}) to the error state. Proof: We will use proof by induction on the length of the input sequences considered. The result holds immediately for the base case, which is the empty sequence, since the empty sequence cannot separate two FSMs and also cannot take a product machine to the error state. Inductive hypothesis: the result holds for all input sequences of length less than k ( k>0 ). We therefore assume that \bar{x} has length k and are required to prove that M\not\approx_{\bar{x}}M_{I} if and only if \bar{x} takes P(M,M_{I}) to the error state. We consider the two directions: 1. Assume that M\not\approx_{\bar{x}}M_{I} and we are required to prove that \bar{x} takes P(M,M_{I}) to the error state. If there is a proper prefix \bar{x}_{1} of \bar{x} such that M\not\approx_{\bar{x}_{1}}M_{I} then we can apply the inductive hypothesis to \bar{x}_{1} and we obtain that \bar{x}_{1} takes P(M,M_{I}) to the error state. Thus, \bar{x} takes P(M,M_{I}) to the error state as required. We will therefore assume that no proper prefix of \bar{x} separates M and M_{I} . Since no proper prefix of \bar{x} separates M and M_{I} , there is an input x and input sequence \bar{x}_{1} such that \bar{x}=\bar{x}_{1}x and M\approx_{\bar{x}_{1}}M_{I} . By the inductive hypothesis, \bar{x}_{1} does not take the product machine to the error state. Let (s_{i},q_{i}) denote the state of the Product Machine reached by \bar{x}_{1} . Since M\not\approx_{\bar{x}}M_{I} and M\approx_{\bar{x}_{1}}M_{I} we must have that x separates states s_{i} and q_{i} . But, by the definition of the Product Machine, this means that the transition with starting state (s_{i},q_{i}) and input x takes the Product Machine to the error state as required. 2. Assume that M\approx_{\bar{x}}M_{I} and we are required to prove that \bar{x} does not take P(M,M_{I}) to the error state. Since \bar{x} is non-empty, \bar{x}=\bar{x}_{1}x for some input x and input sequence \bar{x}_{1} . Further, M\approx_{\bar{x}_{1}}M_{I} and so, by the inductive hypothesis, \bar{x}_{1} does not take P(M,M_{I}) to the error state. Let us suppose that \bar{x}_{1} takes P(M,M_{I}) to state (s_{i},q_{i}) . But, since M\approx_{\bar{x}}M_{I} , by definition we have that s_{i}\approx_{x}q_{i} . Thus, by the definition of the Product Machine, there is a transition from (s_{i},q_{i}) to (\delta(s_{i},a),\delta_{I}(q_{i},x)) with input x . Thus, \bar{x} does not take P(M,M_{I}) to the error state as required. ∎ The following is immediate from the above. Proposition 4 Given FSMs M and M_{I} , M_{I} conforms to M if and only if the error state of P(M,M_{I}) is not reachable. Fig. 3: Thermostat System: Product Machines of Conforming and Non-Conforming Implementations Example 5 Consider the two implementations analysed for conformance in Example 3 . Figure 3 depicts the product automaton of the two implementation. As it can be observed in the figure, the product machine concerning \mathit{Implementation}_{0} , does not feature any reachable error state, because all transitions can be matched up to the error margin (of 0.5). However, for \mathit{Implementation}_{1} , due to the dissimilar behaviour observed after the third switch transition, the product machine will move to an error state. III-B Apartness and Strong Separability Previous work has used the notion of an apartness relation and shown how one can use this to reason about test effectiveness when there is a finite set of outputs and conformance is defined in terms of equality of outputs rather than similarity. Definition 8 A binary relation \# on a set Z is an apartness relation if and only if it satisfies the following properties • It is irreflexive: for all x\in Z we have that x\#x does not hold; • It is symmetric: for all x,y\in Z , if x\#y then y\#x ; and • It is co-transitive: for all x,y,z\in Z , if x\#y then either x\#z or y\#z . Consider the classical notion of separability for FSMs defined in Section II (d-separability). It is immediately clear that d-separability is both irreflexive and symmetric. Now let us suppose that input sequence \bar{x} d-separates states s_{1} and s_{2} of M and so \bar{x} leads to different output sequences \bar{y}_{1} and \bar{y}_{2} when applied in s_{1} and s_{2} . Further, let us suppose that we input \bar{x} in some other state s_{i} and this leads to output sequence \bar{y} . Since \bar{x} d-separates s_{1} and s_{2} we have that \bar{y}_{1}\neq\bar{y}_{2} . We therefore must have that either \bar{y}\neq\bar{y}_{1} or \bar{y}\neq\bar{y}_{2} (or both) and so \bar{x} must d-separate s_{i} from at least one of s_{1} and s_{2} . As a result, d-separability is co-transitive. From this it is clear that d-separability is an apartness relation when testing a deterministic SUT against a completely-specified deterministic FSM M , with identify rather than similarity, and so the results of Vaandrager [ 27 ] can be applied. Now consider what we mean by separability when we have continuous outputs and similarity is defined in terms of a metric m and a threshold t . Then an input sequence separates states s_{1} and s_{2} if the resultant observations o_{1} and o_{2} are such that m(o_{1},o_{2})>t . In such scenarios, separability is not an apartness relation since it need not be co-transitive, as shown by the following. Example 6 Consider the FSM thermostat models in Example 2 (Figure 2 ); there, consider the states \mathit{Off} and \mathit{On} in the \mathit{Specification} FSM. They are separable using both inputs r and s . Let us consider what happens if we use r to separate these states and we have some state s_{i} of the SUT. Then s_{i} can have r/19.5 , e.g., the state \mathit{Off}_{0} in \mathit{Implementation}_{0} , that cannot be separated using only input r from either of the two states. This shows that separability is not co-transitive and so is not an apartness relation. Since we cannot use the notion of apartness, we explore how this can be weakened for the scenarios of interest. We first discuss how d-separability is used in classical FSM-based test techniques. In most FSM-based test techniques that aim to find state-transfer faults, input sequences that d-separate states of a specification FSM are used to check the current state of the SUT. To see how this works, let us suppose that input sequence \bar{x} d-separates states s_{1} and s_{2} of the specification FSM and that the (expected) output sequences produced are \bar{y}_{1} and \bar{y}_{2} respectively. Let us suppose that \bar{x} is applied to the SUT when the SUT is in some an state s_{i}\not\in\{s_{1},s_{2}\} . There are three possibilities: 1. The SUT produces output sequence \bar{y}_{2} in response to \bar{x} . We thus have that \bar{x} d-separates s_{i} and s_{1} . 2. The SUT produces output sequence \bar{y}_{1} in response to \bar{x} . We thus have that \bar{x} d-separates s_{i} and s_{2} . 3. The SUT produces some other output sequence \bar{y}_{3} in response to \bar{x} . We thus have that \bar{x} d-separates s_{i} and from both s_{1} and s_{2} . FSM-based test techniques utilise such information that is provided by applying input sequences that d-separate the states of the specification. However, in Example 6 we saw that the above does not hold in the scenarios that we consider in this paper: if two states of the specification are separated by an input sequence \bar{x} then it is possible that a state of the SUT is not separated from either of them by \bar{x} . We now strengthen the notion of separability, to what we call strong separability, in a manner that ensures that strong separability satisfies the property (of d-separability in traditional FSM-based testing scenarios) described above. Definition 9 Given FSM M and states s_{1},s_{2}\in S , input sequence \bar{x} is a witness that states s_{1} and s_{2} , s_{1}\neq s_{2} , are strongly separable , denoted s_{1}\#^{w}_{\bar{x}}s_{2} , if and only if for all s_{3}\in{\mathcal{F}} we have that either s_{1}\not\approx_{\bar{x}}s_{3} or s_{2}\not\approx_{\bar{x}}s_{3} . We also say that s_{1} and s_{2} are strongly separable and denote this s_{1}\#^{w}s_{2} . Example 7 Consider the FSM thermostat models in Example 2 (Figure 2 ). Recall that states \mathit{Off} and \mathit{On} in the \mathit{Specification} FSM are separable using both inputs r and s . However, we have seen that they are not strongly separable using input r . Namely, there can be a state that has r/19.5 , e.g., the state \mathit{Off}_{0} in \mathit{Implementation}_{0} , that cannot be separated using only input r from either of the two states. In such cases, one can fix this issue, i.e., obtain strong separability, by either choosing different input sequences (in this case s ) or decreasing the threshold of similarity, e.g., to 0.1 , so that all possible states in {\mathcal{F}} are separable (by r ) from at least one of these two states. In practice, the use of a lower threshold might require changes to the equipment used to observe the SUT in testing or to additional test runs with the same input sequence (so that more precise estimates are produced). The following proposition states and proves the basic properties of strong separability. Proposition 5 Given FSM M and input sequence \bar{x} , the relation \#^{w}_{\bar{x}} is symmetric and irreflexive. Proof: The symmerry of relation \#^{w}_{\bar{x}} is immediate from Definition 9 . To prove that \#^{w}_{\bar{x}} is irreflexive, we use a proof by contradiction and assume that there is an input sequence \bar{x} and state s_{i} such that s_{i}\#^{w}_{\bar{x}}s_{i} . Choosing s_{3}=s_{i} we then obtain, from Definition 9 , that s_{i}\not\approx_{\bar{x}}s_{i} . However, this contradicts \not\approx_{\bar{x}} being irreflexive and so the result follows. ∎ Using the following proposition, we can compare strongly separability and separability. Proposition 6 Given FSM M , input sequence \bar{x} and states s_{1} and s_{2} of M such that s_{1}\#^{w}_{\bar{x}}s_{2} , we have that \bar{x} separates s_{1} and s_{2} . Proof: Choose s_{3}=s_{1} . By the definition of \#^{w}_{\bar{x}} (Definition 9 ), we must have that either s_{1}\not\approx_{\bar{x}}s_{1} or s_{2}\not\approx_{\bar{x}}s_{1} . Since \not\approx_{\bar{x}} is irreflexive, we therefore have that s_{2}\not\approx_{\bar{x}}s_{1} and so the result follows. ∎ The following is immediate from the definition of strong separability and corresponds to the property (described above) of d-separability in traditional FSM-based testing. Proposition 7 Given states s_{1} and s_{2} of M with s_{1}\#^{w}_{\bar{x}}s_{2} , if s_{3}\in{\mathcal{F}} then at least one of the following must hold. 1. \bar{x} separates s_{3} from s_{1} ; 2. \bar{x} separates s_{3} from s_{2} ; 3. \bar{x} separates s_{3} from both s_{1} and s_{2} . IV Test Generation In this section, we explore the problem of test generation when, for every pair of states of specification M , we have a specific input sequence that provides a witness that these states are strongly separable. Assumption 2 For every pair s_{1},s_{2} of distinct states of M , there is an input sequence \bar{x} that is a witness that s_{1} and s_{2} are strongly separable. We will use w(s_{1},s_{2}) to represent such a witness (and so s_{1}\#^{w}_{w(s_{1},s_{2})}s_{2} ) and require that w(s_{1},s_{2})=w(s_{2},s_{1}) . We will retain the notion of a state cover, used in classical FSM-based test generation techniques. First we define a state cover, which is a minimal prefix-closed set of input sequences that, between them, reach all states of M . Definition 10 Given a finite state machine M whose states are pairwise strongly separable, a set V of input sequences is a state cover for M if V is prefix closed and for all s_{i}\in S there is exactly one input sequence v_{i}\in V such that \delta(s_{0},v_{i})=s_{i} . Example 8 Consider the \mathit{Specification} FSM in Example 2 (Figure 2 ); a state cover set V for \mathit{Specification} is \{\varepsilon,s\} . If we have a set of test sequences Z , we can remove from Z any sequence that is a proper prefix of another sequence in Z . We will let RP(Z) denote the set of input sequences produced by removing from Z any input sequence that is a proper prefix of another input sequence in Z . Definition 11 Given a set Z of input sequences, its irredundant subset, denoted by RP(Z) , is defined as follows: RP(Z)=\{\sigma_{1}\in Z|\nexists\sigma_{2}\in X^{*}\setminus\{\varepsilon\}.\sigma_{1}.\sigma_{2}\in Z\} In the following, for a state s_{i} of M we use W(s_{i}) to denote the set of input sequences used to show that s_{i} is strongly separable from other states of M . Recall that for a pair s_{1},s_{2} of distinct states of M , w(s_{1},s_{2}) denotes a unique input sequence that is a witness for s_{1} and s_{2} being apart. Definition 12 Given state s_{1} of M , we let W(s_{1}) denote the state identification set W(s_{1})=RP(\{w(s_{1},s_{2})|s_{2}\in S\setminus\{s_{1}\}\}) Example 9 Consider the \mathit{Specification} FSM in Example 2 (Figure 2 ). Both r and s pairwise separate the states of \mathit{Specification} but we have seen that only s strongly separates these states: \mathit{Off}\#^{w}_{s}\mathit{On} and \neg\mathit{Off}\#^{w}_{r}\mathit{On} . Since \mathit{Off}\#^{w}_{s}\mathit{On} , we can choose the state identification set for \mathit{Off} (and symmetrically for \mathit{On} ) to be \{s\} . Recall that we do not know the FSM M_{I} that models the SUT but we will want to reason about the states of this unknown FSM that are met during testing. Given a state s_{i} of M , we use B(s_{i}) to denote the ball (set) of states of M_{I} that are not separated from s_{i} by the input sequences in the state identification set for s_{i} . Definition 13 Given state s_{i} of M and FSM M_{I} with state set Q , B(s_{i})=\{q\in Q|\forall w\in W(s_{i}).s_{i}\approx_{w}q\} . Example 10 Consider the \mathit{Specification} and \mathit{Implementation}_{0} FSMs in Example 2 (Figure 2 ), comprising the set of states \{\mathit{Off},\mathit{On},\mathit{Off}_{0},\mathit{On}_{0}\} . We therefore have that Q=\{\mathit{On}_{0},\mathit{Off}_{0}\} . Given the identification set \{s\} , we have that B(\mathit{Off})=\{\mathit{Off}_{0}\} and B(\mathit{On})=\{\mathit{On}_{0}\} . Clearly we have that B(\mathit{On}) and B(\mathit{Off}) are disjoint. Observe that B(s_{i}) is defined in terms of separability and not strong separability. However, the notion of state identifier used in Definition 13 is defined in terms of strong separability (see Definition 9 ). The following shows what can happen if we were to instead use input sequences that separate, but do not strongly separate, the states of the specification. Example 11 Consider again the \mathit{Specification} and \mathit{Implementation}_{0} FSMs in Example 2 (Figure 2 ), comprising the set of states \{\mathit{Off},\mathit{On},\mathit{Off}_{0},\mathit{On}_{0}\} , with Q=\{\mathit{On}_{0},\mathit{Off}_{0}\} . Now consider the input r , which separates the states of the specification, and the sets B_{1}=\{q\in Q|q\sim_{r}\mathit{Off}\} and B_{2}=\{q\in Q|q\sim_{r}\mathit{On}\} . We have that B_{1}=\{\mathit{Off}_{0}\} and B_{2}=\{\mathit{On}_{0},\mathit{Off}_{0}\} . In this case, B_{1} and B_{2} are not disjoint. The following is an important consequence of strong separability and tells us that if we take two strongly separable states s_{1} and s_{2} of M then B(s_{1}) and B(s_{2}) are pairwise disjoint (ie the property we observed in Example 10 always holds). Proposition 8 Given states s_{1} and s_{2} of M with s_{1}\#^{w}_{\bar{x}}s_{2} , if s^{\prime}_{1}\in B_{\bar{x}}(s_{1}) and s^{\prime}_{2}\in B_{\bar{x}}(s_{2}) then s^{\prime}_{1}\neq s^{\prime}_{2} . Proof: We use a proof by contradiction, assuming that there is a state q of M_{I} such that q\in B_{\bar{x}}(s_{1})\cap B_{\bar{x}}(s_{2}) . By the definition of strong separability (Definition 9 ), since s_{1}\#^{w}_{\bar{x}}s_{2} , either q\not\approx_{\bar{x}}s_{1} or q\not\approx_{\bar{x}}s_{2} . The first of these contradicts q\in B_{\bar{x}}(s_{1}) and the second contradicts q\in B_{\bar{x}}(s_{2}) . The result thus follows. ∎ The test generation approach will be based on placing a lower bound on the number of states M_{I} must have if the SUT is faulty and it passes all the test cases in a given test suite. The approach will use Proposition 8 , which tells us that if two input sequences \bar{x}_{1} and \bar{x}_{2} reach states s_{1} and s_{2} of M respectively, \bar{x} strongly separates s_{1} and s_{2} (ie s_{1}\#^{w}_{\bar{x}}s_{2} ), and the SUT conforms to the SUT on both \bar{x}_{1}.\bar{x} and \bar{x}_{2}.\bar{x} then \bar{x}_{1} and \bar{x}_{2} must reach different states of M_{I} . We now consider what we know about the states of the SUT reached by the state cover V if M_{I} conforms to M on the set of input sequences formed by following each sequence in V by the corresponding state identification set. Proposition 9 Let V be a state cover for FSM M whose states are pairwise strongly separable. Further, let us suppose that every pair (s_{i},q_{i}) of states of the product machine P(M,M_{I}) reached by a trace in V satisfies the property that s_{i}\approx_{W(s_{i})}q_{i} . Then V reaches n separate states of M_{I} . Proof: Since V contains n traces, it is sufficient to prove that if v_{1} and v_{2} are different input sequences in V then they reach different states of M_{I} . Let us suppose that v_{1}\neq v_{2} and also that v_{1} and v_{2} reach the states (s_{1},q_{1}) and (s_{2},q_{2}) of P(M,M_{I}) respectively. There is some witness w(s_{1},s_{2}) that s_{1} and s_{2} are strongly separable and we will use \bar{x} to denote w(s_{1},s_{2}) . We know that s_{1}\#^{w}_{\bar{x}}s_{2} , s_{1}\approx_{\bar{x}}q_{1} and s_{2}\approx_{\bar{x}}q_{2} . But, by Proposition 8 , this means that q_{1}\neq q_{2} and so v_{1} and v_{2} reach different states of M_{I} . ∎ Example 12 Following up on Examples 8 , 9 , and 10 , consider the state cover set \{\varepsilon,s\} and the state identification set \{s\} for which the states of specification are strongly separable. Now consider \mathit{Implementation}_{0} ; the state cover set of the specification will take \mathit{Implementation}_{0} to \mathit{Off}_{0} and \mathit{On}_{0} , which are clearly different states. The same observation can be made for \mathit{Implementation}_{1} . Note that by bringing \mathit{Specification} and \mathit{Implementation}_{1} using s to (\mathit{On},\mathit{On}_{1}) and performing the state identification sequence s from there, we arrive at (\mathit{Off},\mathit{On}_{1}) , which are not similar and will be distinguished using one further input, i.e., by applying the state identification sequence. This is formalised in the subsequent results. The test generation techniques that we build upon use input sequences of the form v.\bar{x}.w such that v is a sequence in the state cover V , \bar{x} is any input sequence of a given length \ell (determined by the maximum number of extra states in the SUT), and w is a state identifier for the state \delta(s_{0},v.\bar{x}) of M . There are two ways in which such an input sequence can lead to a failure being observed. 1. The SUT M_{I} does not conform to the specification M on the initial sequence v.\bar{x} . If the SUT has output faults (one or more transitions produce the wrong output) then these output faults will lead to such failures. 2. There are v , \bar{x} , and w such that the SUT M_{I} does conform to the specification M on the initial sequence v.\bar{x} but does not conform to the specification on v.\bar{x}.w . In this case, a state identifier for \delta(s_{0},v.\bar{x}) separates the state of the SUT M_{I} reached by v.\bar{x} from the state of the specification M reached by v.\bar{x} . The following introduces corresponding notation, for a fixed length \ell of input sequence \bar{x} . Definition 14 Let us suppose that all states of FSM M are strongly separable and M_{I} is an FSM with the same input and output alphabets as M . Further, let us suppose that V is a state-cover for M and for all s_{i}\in S we have that W(s_{i}) is a state identification set for s_{i} . Given integer \ell>0 : \begin{array}[]{lcl}D(M,M_{I},V,\ell)&=&\{(v,\bar{x})|v\in V\wedge|\bar{x}|=\ell\wedge\\ &&~~M\not\approx_{v\bar{x}}M_{I}\}\\ DW(M,M_{I},V,W,\ell)&=&\{(v,\bar{x})|v\in V\wedge|\bar{x}|=\ell\wedge\\ &&~~\exists w\in W(\delta(s_{0},v\bar{x})).\\ &&~~M\not\approx_{v\bar{x}w}M_{I}\}\end{array} We now provide two results that show what one can deduce from the value of the smallest integer \ell such that D(M,M_{I},V,\ell)\cup DW(M,M_{I},V,W,\ell)\neq\emptyset . Given this \ell , we will place a lower bound on the number of different states of M_{I} reached by V and sequences of the form v.\bar{x} , for v\in V and input sequence \bar{x} of length at most \ell (Proposition 10 ). We then show that this implies an upper bound on the value of \ell that we need to use in testing (Proposition 11 ). Lemma 1 Let us suppose that all states of FSM M are strongly separable and for all v\in V and w\in W(\delta(s_{0},v)) we have that M\approx_{vw}M_{I} . Let us also suppose that M_{I} does not conform to M and \ell>0 is the smallest value such that D(M,M_{I},V,\ell)\cup DW(M,M_{I},V,W,\ell)\neq\emptyset . If (v,\bar{x})\in D(M,M_{I},V,\ell)\cup DW(M,M_{I},V,W,\ell) and \bar{x}_{1} is a non-empty proper prefix of \bar{x} then the state of M_{I} reached by v\bar{x}_{1} is not a state of M_{I} reached by an input sequence in V . Proof: Since \bar{x}_{1} is a non-empty proper prefix of \bar{x} , there is some non-empty input sequence \bar{x}_{2} such that \bar{x}=\bar{x}_{1}\bar{x}_{2} . Further, by the minimality of \ell , M_{I} must conform to M on v\bar{x}_{1} and so, by Proposition 3 , v\bar{x}_{1} does not take the product machine to the error state. Let us suppose that (s_{1},q_{1}) is the state of the product machine P(M,M_{I}) reached by v\bar{x}_{1} . By the minimality of \ell , we must have that q_{1}\in B(s_{1}) . Let v_{2} be some input sequence in V and let us suppose that v_{2} reaches the state (s_{2},q_{2}) of PM(M,M_{I}) . It is therefore sufficient to prove that q_{1}\neq q_{2} . Since for all v\in V and w\in W(\delta(s_{0},v)) we have that M\approx_{vw}M_{I} , we know that q_{2}\in B(s_{2}) . There are now two cases to consider. 1. Case 1: s_{1}\neq s_{2} . Let w=w(s_{1},s_{2}) . We have that s_{1}\#^{w}_{w}s_{2} , q_{1}\in B(s_{1}) and q_{2}\in B(s_{2}) . By Proposition 8 we have that q_{1}\neq q_{2} as required. 2. Case 2: s_{1}=s_{2} . We use proof by contradiction and assume that q_{1}=q_{2} . This means that the states of the product machine P(M,M_{I}) reached by v_{2} and v\bar{x}_{1} are the same. There are two cases. (a) Case 2a: (v,\bar{x})\in D(M,M_{I},V,\ell) and so M\not\approx_{v\bar{x}}M_{I} . By the minimality of \ell , we have that M\approx_{v\bar{x}_{1}}M_{I} . Since M\not\approx_{v\bar{x}}M_{I} and \bar{x}=\bar{x}_{1}\bar{x}_{2} we therefore have that s_{1}\not\approx_{\bar{x}_{2}}q_{1} . But, since v_{2} takes the product machine PM(M,M_{I}) to state (s_{2},q_{2})=(s_{1},q_{1}) , we have that M\not\approx_{v_{2}\bar{x}_{2}}M_{I} . Since \bar{x}_{2} is shorter than \bar{x} , this tells us that there is some \ell^{\prime}<\ell such that D(M,M_{I},V,\ell)\neq\emptyset . This contradicts the minimality of \ell as required. (b) Case 2b: (v,\bar{x})\in DW(M,M_{I},V,W,\ell) and so there exists w\in W(s_{1}) such that M\not\approx_{v\bar{x}w}M_{I} . By the minimality of \ell , we have that M\approx_{v\bar{x}_{1}}M_{I} . Since M\not\approx_{v\bar{x}w}M_{I} we therefore have that s_{1}\not\approx_{\bar{x}_{2}w}q_{1} . But, since v_{2} takes the product machine PM(M,M_{I}) to state (s_{2},q_{2})=(s_{1},q_{1}) , we have that M\not\approx_{v_{2}\bar{x}_{2}w}M_{I} . Since \bar{x}_{2} is shorter than \bar{x} , there is some \ell^{\prime}<\ell such that DW(M,M_{I},V,W,\ell^{\prime})\neq\emptyset . This contradicts the minimality of \ell as required. ∎ Lemma 2 Let us suppose that all pairs of states of FSM M are strongly separable and for all v\in V and w\in W(\delta(s_{0},v)) we have that M\approx_{vw}M_{I} . Further, let us suppose that M_{I} does not conform to M and \ell>0 is the smallest value such that D(M,M_{I},V,\ell)\cup DW(M,M_{I},V,W,\ell)\neq\emptyset . If (v,\bar{x})\in D(M,M_{I},V,\ell)\cup DW(M,M_{I},V,W,\ell) and \bar{x}_{1},\bar{x}_{2} are different non-empty proper prefixes of \bar{x} then v\bar{x}_{1} and v\bar{x}_{2} reach different states of M_{I} . Proof: First, by Proposition 3 , v\bar{x}_{1} and v\bar{x}_{2} do not take the product machine to the error state. Let us suppose that (s_{1},q_{1}) is the state of the product machine P(M,M_{I}) reached by v\bar{x}_{1} and (s_{2},q_{2}) is the state of the product machine P(M,M_{I}) reached by v\bar{x}_{2} . There are two cases to consider. 1. Case 1: s_{1}\neq s_{2} . Let w=w(s_{1},s_{2}) . We have that s_{1}\#^{w}_{w}s_{2} , q_{1}\in B(s_{1}) and q_{2}\in B(s_{2}) . By Proposition 8 we have that q_{1}\neq q_{2} as required. 2. Case 2: s_{1}=s_{2} . We use proof by contradiction and assume that q_{1}=q_{2} . We therefore have that v\bar{x}_{1} and v\bar{x}_{2} reach the same states of the product machine P(M,M_{I}) . Without loss of generality assume that \bar{x}_{1} is a proper prefix of \bar{x}_{2} and define \bar{x}_{3} by \bar{x}=\bar{x}_{2}\bar{x}_{3} . There are two cases. (a) Case 2a: (v,\bar{x})\in D(M,M_{I},V,\ell) and so M\not\approx_{v\bar{x}}M_{I} . By the minimality of \ell , we have that M\approx_{v\bar{x}_{2}}M_{I} . Since M\not\approx_{v\bar{x}}M_{I} and \bar{x}=\bar{x}_{2}\bar{x}_{3} we therefore have that s_{2}\not\approx_{\bar{x}_{3}}q_{2} . But, since v\bar{x}_{1} takes the product machine PM(M,M_{I}) to state (s_{1},q_{1})=(s_{2},q_{2}) , we have that M\not\approx_{v\bar{x}_{1}\bar{x}_{3}}M_{I} . Since \bar{x}_{1}\bar{x}_{3} is shorter than \bar{x} this tells us that there is some \ell^{\prime}<\ell such that D(M,M_{I},V,\ell^{\prime})\neq\emptyset . This contradicts the minimality of \ell as required. (b) Case 2b: (v,\bar{x})\in DW(M,M_{I},V,W,\ell) and so there exists w\in W(\delta(s_{0},v\bar{x})) such that M\not\approx_{v\bar{x}w}M_{I} . By the minimality of \ell , we have that M\approx_{v\bar{x}_{2}}M_{I} . Since M\not\approx_{v\bar{x}w}M_{I} we therefore have that s_{2}\not\approx_{\bar{x}_{3}w}q_{2} . But, since v\bar{x}_{1} takes the product machine PM(M,M_{I}) to state (s_{1},q_{1})=(s_{2},q_{2}) , we have that M\not\approx_{v\bar{x}_{1}\bar{x}_{3}w}M_{I} . Since \bar{x}_{1}\bar{x}_{3} is shorter than \bar{x} , this tells us that there is some \ell^{\prime}<\ell such that DW(M,M_{I},V,W,\ell^{\prime})\neq\emptyset . This contradicts the minimality of \ell as required. ∎ Example 13 For the non-conforming implementation \mathit{Implementation}_{1} , we have that it is sufficient to take \bar{x} to be s since after s\in V and s\in W , a further input s can reach a non-conformance verdict between the specification and the implementation. This is because the faulty implementation does not have any additional state with respect to the specification. For faulty implementations with additional states, we may need longer intermediate inputs to reach non-conformance but there is a fixed upper bound given an upper bound on the size of the implementation, as stated below. In terms of Definition 14 this is summarised as follows, where, and for brevity we refer to the specification as M and to \mathit{Implementation}_{1} as M_{I} : \begin{array}[]{lcl}D(M,M_{I},V,1)&=&\emptyset\\ DW(M,M_{I},V,W,1)&=&\{(s,s)\}\end{array} Note that D(M,M_{I},V,1) is the empty set because the pair with the shortest sequence to distinguish M and M_{I} is (s,s.s) , of which the second component is beyond the allowed limit of l=1 . However, DW(M,M_{I},V,W,1) contains the pair (s,s) , because after s.s by performing a further s\in W , we can distinguish the two systems. We can use the above-given Lemmas to place a lower bound on the number of states an SUT must have if the SUT is faulty and we know the smallest value \ell such that D(M,M_{I},V,\ell)\cup DW(M,M_{I},V,W,\ell)\neq\emptyset . Proposition 10 Let us suppose that all pairs of states of FSM M are strongly separable, M_{I} does not conform to M , and for all v\in V and w\in W(\delta(s_{0},v)) we have that M\approx_{vw}M_{I} . If \ell is the smallest value such that D(M,M_{I},V,\ell)\cup DW(M,M_{I},V,W,\ell)\neq\emptyset then M_{I} has at least n+\ell-1 states. Proof: First recall that, by Proposition 9 , V reaches n separate states of M_{I} . Let (v,\bar{x}) be some pair in D(M,M_{I},V,\ell)\cup DW(M,M_{I},V,W,\ell) . By Lemma 1 , if \bar{x}_{1} is a non-empty proper prefix of \bar{x} then the state of M_{I} reached by v\bar{x}_{1} is not a state of M_{I} reached by V . Thus the number of states of M_{I} must be at least n=|V| plus the number of states of M_{I} reached by sequences of the form v\bar{x}_{1} where \bar{x}_{1} is a non-empty proper prefix of \bar{x} . We now need to consider how many different states of M_{I} are reached by sequences of the form v\bar{x}_{1} where \bar{x}_{1} is a non-empty proper prefix of \bar{x} . Lemma 2 tells us that if \bar{x}_{1} and \bar{x}_{2} are different non-empty proper prefixes of \bar{x} then v\bar{x}_{1} and v\bar{x}_{2} reach different states of M_{I} . Thus, the number of different states of M_{I} reached by sequences of the form v\bar{x}_{1} , where \bar{x}_{1} is a non-empty proper prefix of \bar{x} , is equal to the number of different non-empty proper prefixes of \bar{x} and that is |\bar{x}|-1 . Bringing these together, we have that the sequences in V reach n different states of M_{I} and the sequences of the form v\bar{x}_{1} , where \bar{x}_{1} is a non-empty proper prefix of \bar{x} , reach another |\bar{x}|-1 states of M_{I} . Thus, M_{I} must have at least n+|\bar{x}|-1 states. It is now sufficient to observe that, by definition, |\bar{x}|=\ell . ∎ Now consider the standard FSM-based testing context in which we assume that the FSM M_{I} that models the SUT has at most n+k states and we wish to generate sufficient tests to determine whether M_{I} conforms to M . We can use the above result (Proposition 10 ) to provide an upper bound on the value of \ell that we require to use when testing with sequences of the form v.\bar{x} and v.\bar{x}.w , with |\bar{x}|\leq\ell . Proposition 11 Let us suppose that all pairs of states of FSM M are strongly separable, M_{I} does not conform to M , and for all v\in V and w\in W(\delta(s_{0},v)) we have that M\approx_{vw}M_{I} . If M_{I} has at most k more states than M then there exists some v\in V , and \bar{x}\in X^{*} such that |\bar{x}|\leq k+1 and one of the following holds: • M_{I}\not\approx_{v\bar{x}}M ; or • there is some w\in W(\delta(s_{0},v\bar{x})) such that M_{I}\not\approx_{v\bar{x}w}M . Proof: This follows from Proposition 10 through a proof by contradiction. ∎ The following shows what this implies regarding test completeness. Theorem 1 Let us suppose that all pairs of states of FSM M are strongly separable, M has n states, and M_{I} has at most m=n+k states. If D(M,M_{I},V,\ell)=\emptyset and DW(M,M_{I},V,W,\ell)=\emptyset for all \ell\leq k+1 then M_{I} conforms to M . Proof: This follows from Proposition 11 . ∎ This result shows how test generation can proceed: one simply uses the test sequences implicit in the definitions of D(M,M_{I},V,\ell) and DW(M,M_{I},V,W,\ell) . Algorithm 1 gives the corresponding test generation algorithm. Note that for a state s_{i} of M , W(s_{i}) is a Harmonized State Identifier for s_{i} as used in the HSI-method except that we require W(s_{i}) to strongly separate s_{i} from other states of M ; it is not sufficient that W(s_{i}) to separates s_{i} from other states of M . As a result, Algorithm 1 is essentially the HSI-method, with the only difference being how we define conformance and the W(s_{i}) . Since the test set produced by the HSI-method is a subset of those produced by the W-method and the Wp-method, the above demonstrates that these test generation techniques also produce m -complete test sets when we have a notion of similarity of outputs rather than equality and we use state identifiers that strongly separate states. Algorithm 1 Test Generation: The HSI Method Using Strong Separability Input: FSM M=(S,s_{0},X,Y,\delta,\lambda) where S=\{s_{1},\ldots,s_{n}\} , m\geq n Derive state cover V Derive state identification sets W(s_{1}),\ldots,W(s_{n}) based on strong separability Derive T=\{v.\bar{x}.w|v\in V,\bar{x}\in X^{*},0\leq|\bar{x}|\leq m-n+1,w\in W(\delta(s_{0},v.\bar{x}))\} Remove from T all prefixes (ie T=RP(T) ) return T Example 14 Consider the \mathit{Specification} FSM in Figure 2 . We have already established in Example 8 that V=\{\varepsilon,s\} and in Example 9 that the state-identification set that strongly separates the specification states is W=\{s\} . Hence, assuming that we are only interested in implementations that have the same state count as the specification, by applying Algorithm 1 , we obtain: \begin{array}[]{lcl}T&=&RP(\{v.\bar{x}.w|v\in\{\varepsilon,s\}\wedge\bar{x}\in\{\varepsilon,r,s\}\wedge w\in\{s\}\})\\ T&=&RP(\{\varepsilon.\varepsilon.s,\varepsilon.r.s,\varepsilon.s.s,s.r.s,s.s.s\})\\ &=&RP(\{s,r.s,s.s,s.r.s,s.s.s\})\\ &=&\{r.s,s.r.s,s.s.s\}\end{array} Note that the key difference between this set of generated inputs and the traditional HSI method is that the adapted algorithm forces the state-identification set to provide strong separability. Otherwise, the traditional HSI method can use r to separate states and generate r.r , s.s.r and s.r.r as the longest sequences and these sequences will miss the fault in \mathit{Implementation}_{1} . This demonstrates that the HSI method, with state identifiers that do not strongly separate the states of the specification, is not complete. Using this specification FSM, state cover, and state identifiers, the W-method and Wp-method return the same test suite and so are also incomplete. It is now worth considering how large the test suite can be for an FSM specification M with n states. Clearly V contains n input sequences and these have length at most n-1 : we can generate such input sequences through a breadth-first search. Further, each W(s_{i}) contains at most n-1 sequences. The following places an upper bound on the lengths of sequences in W(s_{i}) , assuming we use shortest sequences that suffice. Proposition 12 Let us suppose that M is an FSM with n states and all pairs of states of M are strongly separable. For every pair s_{1},s_{2} of distinct states of M , there is an input sequence of length at most \frac{n(n-1)}{2} that strongly separates s_{1} and s_{2} . Proof: Given any pair (s_{1},s_{2}) of distinct states of M let d(s_{1},s_{2}) denote the length of the shortest input sequence(s) that strongly separate s_{i} and s_{j} . Choose two states s_{1} and s_{2} and let us suppose that d(s_{1},s_{2})=a . It is sufficient to prove that a\leq\frac{n(n-1)}{2} . Let \bar{x}=x_{1}\ldots x_{a} be a shortest input sequence that strongly separates s_{1} and s_{2} . For i\in\{1,2\} and 1\leq j