## Distinguishing Tests for Nondeterministic and Probabilistic Machines

*Rajeev Alur, Costas Courcoubetis, and
Mihalis Yannakakis*
We study the problem of uniquely identifying the initial state
of a given finite-state machine from among a set of possible choices,
based on the input-output behavior.
Equivalently, given a set of machines, the problem is to design a test
that distinguishes among them.
We consider nondeterministic machines as well as probabilistic machines.
In both cases, we show that it is PSPACE-complete to decide whether
there is a preset distinguishing
strategy (i.e. a sequence of inputs fixed in advance),
and it is EXPTIME-complete to decide whether there is an adaptive
distinguishing strategy (i.e. when the next input can be chosen based
on the outputs observed so far).
The probabilistic testing is closely related to probabilistic games,
or Markov Decision Processes, with incomplete information.
We also provide optimal bounds for deciding whether such games have
strategies winning with probability 1.

*Proceedings of the
27th ACM Symposium on Theory of Computing*
(STOC 1995), pp. 363-372.