Weighted finite automata over strong bimonoids |
| |
Authors: | Manfred Droste Torsten Stüber Heiko Vogler |
| |
Affiliation: | a Institut für Informatik, Universität Leipzig, D-04009 Leipzig, Germany b Faculty of Computer Science, Technische Universität Dresden, D-01062 Dresden, Germany |
| |
Abstract: | We investigate weighted finite automata over strings and strong bimonoids. Such algebraic structures satisfy the same laws as semirings except that no distributivity laws need to hold. We define two different behaviors and prove precise characterizations for them if the underlying strong bimonoid satisfies local finiteness conditions. Moreover, we show that in this case the given weighted automata can be determinized. |
| |
Keywords: | Weighted automata Bimonoids Formal power series Determinizability Multi-valued automata |
本文献已被 ScienceDirect 等数据库收录! |