On Minimizing Weighted Finite Automata
Date Issued
2008
Date
2008
Author(s)
Huang, Ting-Yuan
Abstract
Weighted Finite Automata represent a very general model which has many different names such as probabilistic finite automata (PFA), hidden Markov models (HMM), stochastic regular grammars, Markov chains and n-grams. These models play central roles in many domains such as machine learning, speech processing, computational linguistics, pattern recognition, language modeling, bioinformatics, music modeling, circuit testing, image processing, path query and time series analysis. The huge number of applications makes weighted finite automata a very valuable research topic: Even a very small breakthrough or improvement would benefit lots of domains. In this thesis, we introduce the notion of “weight redistribution” by investigating the algebraic properties along with the graphical structure inside weighted finite automata. We also generalize the concept of shortest-path problem to finding infimum along every paths and give an effcient algorithm to solve it. Our algorithm to compute “weight redistribution” not only plays the central role in our minimization algorithm, but also is applicable on determining the equivalence Z-automata. We also give two new algorithms to shrink the state space. These algorithms outperform pervious results.
Subjects
weighted finite automata
Minimization
probabilistic finite automata
hidden Markov model
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R95921091-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):3af08017f536dc7fee9db5cbee0e21f6