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 (λ, μ, γ), 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 n×n 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) γ&bne;(S, c) and the coefficient (S, c) are
社団法人電子情報通信学会の論文
1994-10-25