Error quantification and recognition using weighted finite automata | Posted on:2008-03-07 | Degree:M.Sc | Type:Thesis | University:Queen's University (Canada) | Candidate:Schofield, Paul M | Full Text:PDF | GTID:2448390005976413 | Subject:Computer Science | Abstract/Summary: | | Weighted finite automata (WFA) are a family of computational models used for tasks as varied as image processing, functional computation and speech recognition. In this thesis, we study WFA for a different application, namely error quantification and recognition. We begin by constructing automata models accepting words within a given error bound from a language. The amount of error is measured using a suitable distance metric.; Previously it had been shown that when an additivity condition is met by a distance metric, any neighbourhood of a regular language using this metric will be regular. We expand upon this result by providing constructions producing deterministic and nondeterministic automata accepting the language of an additive WFA within a given error bound.; We then present a result giving the upper bound for the state complexity of the additive WFA to deterministic finite automaton (WFA-to-DFA) conversion. Having implemented the WFA to nondeterministic finite automaton (WFA-to-NFA) and WFA-to-DFA conversions, we identify languages exhibiting the upper bound in state complexity for the WFA-to-DFA conversion. We use these identified languages to prove a lower bound for one family of languages, thereby showing that the upper bound of the conversion is tight.; We show that for any regular language, we can construct an additive WFA accepting a neighbourhood of the language with respect to an additive distance metric. Also, we show that any language accepted by an additive WFA within a given error bound, is regular. | Keywords/Search Tags: | WFA, Error, Finite, Automata, Distance metric, Language, Recognition, Using | | Related items |
| |
|