  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 is widely used, e.g., to check conformance of protocol
implementations, its applicability is limited by restrictions of the FSM
framework: the fact that inputs and outputs alternate in an FSM, and outputs
are fully 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 & Yannakakis. Our algorithm has to deal with so-called
compatible states, states that cannot be distinguished in case of an
adversarial system-under-test. Analogous to the result of Lee & 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
adaptive tests typically do not exist. However, in experiments with an
implementation of our algorithm on an industrial benchmark, we find that tests
produced by our algorithm still distinguish more than 99% of the incompatible
state pairs.
