An improved algorithm for determinization of weighted and fuzzy automata |
| |
Authors: | Zorana Jan?i? Miroslav ?iri? |
| |
Affiliation: | University of Niš, Faculty of Sciences and Mathematics, Višegradska 33, 18000 Niš, Serbia |
| |
Abstract: | For a given weighted finite automaton over a strong bimonoid we construct its reduced Nerode automaton, which is crisp-deterministic and equivalent to the original weighted automaton with respect to the initial algebra semantics. We show that the reduced Nerode automaton is even smaller than the Nerode automaton, which was previously used in determinization related to this semantics. We determine necessary and sufficient conditions under which the reduced Nerode automaton is finite and provide an efficient algorithm which computes the reduced Nerode automaton whenever it is finite. In determinization of weighted finite automata over semirings and fuzzy finite automata over lattice-ordered monoids this algorithm gives smaller crisp-deterministic automata than any other known determinization algorithm. |
| |
Keywords: | Weighted automaton Strong bimonoid Fuzzy automaton Formal power series Determinization Nerode automaton |
本文献已被 ScienceDirect 等数据库收录! |