Distinguishing tests for nondeterministic and probabilistic machines
Rajeev Alur, Costas Courcoubetis, Mihalis Yannakakis · 1995
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. 1 Introduction Finite-state machines have been widely used to model systems in diverse areas o...