Bounded sequence testing from deterministic finite state machines

Abstract: The - and -methods are the basis for conformance testing from a deterministic finite state machine (DFSM) when the conformance relation considered is equivalence. However, many DFSM applications use only input sequences of limited length. In such cases, the test data only need to establish that the implementation under test produces the specified responses for sequences of length less than or equal to the upper bound . This paper extends the - and -methods to the case in which only bounded sequences are allowed. The methods for bounded sequences are stronger than the originals since test suites for the unbounded case can be obtained as a particular case (in which the upper bound is sufficiently large) from the new formulae. Furthermore, the generalization is not straightforward as it is not sufficient to extract the sequences of length at most from the test suites produced in the unbounded case, or even all prefixes of length at most of the original test sequences. The practicality of the methods is also improved in comparison to the unbounded case: the size of the test suites may be considerably reduced while the complexity of the test generation algorithms remains basically unchanged. [Copyright &y& Elsevier]