Determinizations Of Weighted Finite Automata Over Commutative Idempotent Semirings

As we know, each finite state automaton is equivalent to a detertminate finite automaton. Unfortunately, not any weighted finite automaton is equivalent to a subsequential weighted finite automaton. Therefore, it is a meaningful topic to consider that which weighted finite automata have subsequential equivalences.To investigate the existence of the subsequential equivalence of a weighted finite automaton over a commutative min-semiring, the authors of [1] proposed the concept of a maximal factorization of finite dimension over a semiring, and then give a sufficient condition for a weighted finite automaton over a commutative min-semiring having a subsequential equivalence.In this paper, we first prove that a commutative semiring K has a maximal factorization of dimension n≥2 if and only if K is a multiplicatively cancellative semiring satisfying the g.c.d. condition. And then, we obtain the result that, if K is a commutative idempotent semiring admitting a maximal factorization of dimension n≥2 and T is a weighted finite automaton over K which has the victory property and the twins property, then T has a subsequential equivalence. The second result is an answer of the open problem raised by the authors of [1]. Furthermore, by using this result, we can also improve the main theorem of the reference [1].