EXACTLY LEARNING AUTOMATA OF SMALL COVER TIME

We present algorithms for exactly learning unknown environments that c an be described by deterministic finite automata. The learner performs a walk on the target automaton, where at each step it observes the ou tput of the state it is at, and chooses a labeled edge to traverse to the next stare. The learner has no means of a reset, and does not have access to a teacher that answers equivalence queries and gives the le arner counterexamples to its hypotheses. We present two algorithms: Th e first is for the case in which the outputs observed by the learner a re always correct, and the second is for the case in which the outputs might be corrupted by random noise. The running times of both algorit hms are polynomial in the cover time of the underlying graph of the ta rget automaton.