Learning Finite Automata Using Local Distinguishing Experiments

Abstract

One of the open problems listed in [Rivest and Schapire, 1989] is whether and how that the copies of L • in their algorithm can be combined into one for better performance. This paper describes an algorithm called v· that does that combination. The idea is to represent the states of the learned model using observable symbols as well as hidden symbols that are constructed during learning. These hidden symbols are created to reflect the distinct behaviors of the model states . The distinct behaviors are represented as local distinguishing experiments (LDEs) (not to be confused with global distinguishing sequences), and these LDEs are created when the learner's prediction mismatches the actual observation from the unknown machine. To synchronize the model with the environment, these LDEs can also be concatenated to form a homing sequence. It can be shown that v· can learn, with probability 1 - e' a model that is an {-approximation of the unknown machine, in a numb er of actions polynomial in the size of the environment and ~(logi)