Authors
Rajeev Alur, Costas Courcoubetis, Mihalis Yannakakis
Publication date
1995/5/29
Book
Proceedings of the twenty-seventh annual ACM symposium on Theory of computing
Pages
363-372
Description
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(ie a sequence of inputs fixed in advance), and it is ExPTIME-complete to decide whether there is an adaptive distinguishing strategy(ie 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.
Total citations
Scholar articles
R Alur, C Courcoubetis, M Yannakakis - Proceedings of the twenty-seventh annual ACM …, 1995