Branch and Bound Algorithm for Phrase Level Pattern Matching By Using Deterministic Context-Free Grammar

概要

論文の詳細を見る
We have been developing a personal speech understanding system by using a pattern maching method. In this paper, we deal with a phrase-level pattern matching algorithm where LR(1)-syntax is processed. We propose a pairwise Markov model (PMM) which is a system to compute likelyhood of an interpretation for an input speech. A PMM has the same syntactic structure as the finite state sequential decision process (fsdp), and is characterized by its base-automaton which is composed through a Cartesian product of two automata. We derive a recurrence equation of a finite state PMM which represents matching of patterns in normal-syntax. We also derive a pattern matching procedure which processes a higher-than-the-normal syntax by using an infinite state PMM (a full PMM). Because of the syntactic equality between a ful1 PMM and an fsdp, we apply the Ibaraki's construction method for an fsdp extensively so that we obtain the pattern matching procedure as a branch-and-bound procedure (named B & B). We construct a pattern matching algotithm which processes an LR(1)-syntax by using the procedure B & B and a given LR(1) parser.
一般社団法人情報処理学会の論文
1988-01-15