A POLYNOMIAL-TIME LEARNING ALGORITHM FOR RECOGNIZABLE SERIES

Recognizable series is a model of a sequential machine. A recognizable series S is represented by a triple (lambda, mu, gamma), called a lin ear representation of S, where lambda is a row vector of dimension n s pecifying the initial state, gamma is a column vector of dimension n s pecifying the output at a state, and mu is a morphism from input words to n x n matrices specifying the state transition. The output for an input word w is defined as lambda(muw)gamma, called the coefficient of w in S, and written as (S, w). We present an algorithm which construc ts a reduced linear representation of an unknown recognizable series S , with coefficients in a commutative field, using coefficient queries and equivalence queries. The answer to a coefficient query, with a wor d w, is the coefficient (S, w) of w in S. When one asks an equivalence query with a linear representation (lambda, mu, gamma), if (lambda, m u, gamma) is a linear representation of S, yes is returned, and otherw ise a word c such that lambda(muc) gamma not-equal (S, c) and the coef ficient (S, c) are returned: Such a word c is called a counterexample for the query. For each execution step of the algorithm, the execution time consumed from the initial step to the current step is O(mN4M), w here N is the dimension of a reduced linear representation of S, M is the maximum time consumed by a single fundamental operation (addition, subtraction, multiplication or division), and m is the maximum length of counterexamples as answers to equivalence queries returned until t hat step.