This conjecture is from an expert in Game Theory area, I post it here to draw more attentions of TCS experts. Discussions and comments are welcome. http://gtcenter.org/WCS_Call_for_papers.pdfAn unknown deterministic finite automaton with a known number of states $n$ is put in a black box. The states of the automaton are colored in two colors, 0 and 1. Given an input bit the automaton outputs the color of its current states and moves to a new state as a function of the current state and the input bit. A decision maker trying to predict the behaviour of the automaton by feeding it input bits and observing the output repeatedly. An attempt is called successful if the input bit is equal to the output bit. How many attempts does the decision maker need until he can succeed in 99% of the attempts (in expectation)? Neyman (1997) showed that $O(n \log n)$ is sufficient and conjectured that $(n\log n)$ is necessary.
Learning Finite Automata Behavior by Experimentation
cc.complexity theory;automata theory