For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE.
 A Polynomial Time Learning Algorithm for Recognizable SeriesHiroyuki OHNISHI  Hiroyuki SEKI  Tadao KASAMI  Publication IEICE TRANSACTIONS on Information and Systems   Vol.E77-D   No.10   pp.1077-1085Publication Date: 1994/10/25Online ISSN:  DOI: Print ISSN: 0916-8532Type of Manuscript: PAPERCategory: Automata, Languages and Theory of ComputingKeyword: computational learning theory,  recognizable series,  automata,  formal language,  Full Text: PDF(669.2KB)>> Buy this Article Summary:  Recognizable series is a model of a sequential machine. A recognizable series S is represented by a triple (λ,µ,γ), called a linear representation of S, where λ is a row vector of dimension n specifying the initial state, γ is a column vector of dimension n specifying the output at a state, and µ is a morphism from input words to nn matrices specifying the state transition. The output for an input word w is defined as λ(µw) γ, called the coefficient of w in S, and written as (S,w). We present an algorithm which constructs 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 word w, is the coefficient (S, w) of w in S. When one asks an equivalence query with a linear representation (λ,µ,γ), if (λ,µ,γ) is a linear representation of S, yes is returned, and otherwise a word c such that λ (µc) γ(S, c) and the coefficient (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(mN 4M), where 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 that step.