Determinization of weighted finite automata over strong bimonoids |
| |
Authors: | Miroslav ?iri? Manfred Droste |
| |
Affiliation: | a Faculty of Sciences and Mathematics, University of Niš, Višegradska 33, P.O. Box 224, 18000 Niš, Serbia b Institut für Informatik, Universität Leipzig, D-04009 Leipzig, Germany c Faculty of Computer Science, Technische Universität Dresden, D-01062 Dresden, Germany |
| |
Abstract: | We consider weighted finite automata over strong bimonoids, where these weight structures can be considered as semirings which might lack distributivity. Then, in general, the well-known run semantics, initial algebra semantics, and transition semantics of an automaton are different. We prove an algebraic characterization for the initial algebra semantics in terms of stable finitely generated submonoids. Moreover, for a given weighted finite automaton we construct the Nerode automaton and Myhill automaton, both being crisp-deterministic, which are equivalent to the original automaton with respect to the initial algebra semantics, respectively, the transition semantics. We prove necessary and sufficient conditions under which the Nerode automaton and the Myhill automaton are finite, and we provide efficient algorithms for their construction. Also, for a given weighted finite automaton, we show sufficient conditions under which a given weighted finite automaton can be determinized preserving its run semantics. |
| |
Keywords: | Weighted automaton Strong bimonoid Formal power series Determinization Nerode automaton Myhill automaton Run automaton |
本文献已被 ScienceDirect 等数据库收录! |
|