The relationships among several forms of weighted finite automata over strong bimonoids

Given a strong bimonoid P, we introduce three different behaviors of a weighted finite automaton over P (called a P−valued finite automaton), named the initial object semantics, final object semantics and run semantics. We define four forms for a P−valued nondeterministic finite automaton (P−NFA) and three forms for a P−valued deterministic finite automaton (P−DFA). Under the above-mentioned semantics, the equivalence and differences among the four forms of P−NFAs are discussed and the equivalence among the three forms of P−DFAs are given. Moreover, we show that some equivalence depends on right distributivity or left distributivity, or even requires P to degenerate into a semiring.