  Model based testing is a well-established approach to verify implementations
modeled by I/O labeled transition systems (IOLTSs). One of the challenges
stemming from model based testing is the conformance checking and the
generation of test suites, specially when completeness is a required property.
In order to check whether an implementation under test is in compliance with
its respective specification one resorts to some form of conformance relation
that guarantees the expected behavior of the implementations, given the
behavior of the specification. The ioco conformance relation is an example of
such a relation, specially suited for asynchronous models. In this work we
study a more general conformance relation, show how to generate finite and
complete test suites, and discuss the complexity of the test generation
mechanism under this more general conformance relation. We also show that ioco
conformance is a special case of this new conformance relation, and we
investigate the complexity of classical ioco-complete test suites. Further, we
relate our contributions to more recent works, accommodating the restrictions
of their classes of fault models within our more general approach as special
cases, and expose the complexity of generating any complete test suite that
must satisfy their restrictions.
