This paper concerns the problem of testing from a partial, possibly non-deterministic, finite state machine (FSM) ${\mathcal S}$<alternatives> <inline-graphic xlink:href="hierons-ieq1-2652457.gif"/></alternatives>. Two notions of correctness (quasi-reduction and quasi-equivalence) have previously been defined for partial FSMs but these, and the corresponding test generation techniques, only apply to FSMs that have harmonised traces. We show how quasi-reduction and quasi-equivalence can be generalised to all partial FSMs. We also consider the problem of generating an $m$<alternatives> <inline-graphic xlink:href="hierons-ieq2-2652457.gif"/></alternatives>-complete test suite from a partial FSM ${\mathcal S}$<alternatives> <inline-graphic xlink:href="hierons-ieq3-2652457.gif"/></alternatives>: a test suite that is guaranteed to determine correctness as long as the system under test has no more than $m$<alternatives><inline-graphic xlink:href="hierons-ieq4-2652457.gif"/> </alternatives> states. We prove that we can complete ${\mathcal S}$<alternatives><inline-graphic xlink:href="hierons-ieq5-2652457.gif"/></alternatives> to form a completely-specified non-deterministic FSM ${\mathcal S}^{\prime}$<alternatives><inline-graphic xlink:href="hierons-ieq6-2652457.gif"/></alternatives> such that any $m$<alternatives> <inline-graphic xlink:href="hierons-ieq7-2652457.gif"/></alternatives>-complete test suite generated from ${\mathcal S}^{\prime}$<alternatives> <inline-graphic xlink:href="hierons-ieq8-2652457.gif"/></alternatives> can be converted into an $m$<alternatives> <inline-graphic xlink:href="hierons-ieq9-2652457.gif"/></alternatives>-complete test suite for ${\mathcal S}$<alternatives> <inline-graphic xlink:href="hierons-ieq10-2652457.gif"/></alternatives>. We also show that there is a correspondence between test suites that are reduced for ${\mathcal S}$ <alternatives><inline-graphic xlink:href="hierons-ieq11-2652457.gif"/></alternatives> and ${\mathcal S}^{\prime}$<alternatives> <inline-graphic xlink:href="hierons-ieq12-2652457.gif"/></alternatives> and also that are minimal for ${\mathcal S}$<alternatives> <inline-graphic xlink:href="hierons-ieq13-2652457.gif"/></alternatives> and ${\mathcal S}^{\prime}$<alternatives> <inline-graphic xlink:href="hierons-ieq14-2652457.gif"/></alternatives>.