State identification for labeled transition systems with inputs and outputs

For Finite State Machines (FSMs) a rich testing theory has been developed to discover aspects of their behavior and ensure their correct functioning. Although this theory has been frequently used, e.g. to check conformance of protocol implementations, its applicability is limited by restrictions of FSMs, in which inputs and outputs alternate, and outputs are determined by the previous input and state. Labeled Transition Systems with inputs and outputs (LTSs), as studied in ioco testing theory, provide a richer framework for testing component oriented systems, but lack the algorithms for test generation from FSM theory. In this article, we propose an algorithm for the fundamental problem of state identification during testing of LTSs. Our algorithm is a direct generalization of the well-known algorithm for computing adaptive distinguishing sequences for FSMs proposed by Lee and Yannakakis. Our algorithm has to deal with so-called compatible states, states that cannot be distinguished. Analogous to the result of Lee and Yannakakis, we prove that if an adaptive test exists that distinguishes all pairs of (incompatible) states of an LTS, our algorithm will find one. In practice, such perfect adaptive tests typically do not exist. However, in experiments with an implementation of our algorithm on a collection of (both academic and industrial) benchmarks, we find that that the adaptive tests produced by our algorithm still distinguish at least 99% of the incompatible state pairs.