On the Determinization of Weighted Automata

In the paper, we generalize an algorithm and some related results by Mohri [25] for deter-minization of weighted finite automata (WFA) over the tropical semiring. We present the underlying mathematical concepts of his algorithm in a precise way for arbitrary semirings. We define a class of semirings in which we can show that the twins property is sufficient for the termination of the algorithm. We also introduce single-valued WFA and give a partial correction of a claim by Mohri [25] by showing several characterizations of single-valued WFA, e.g., the formal power series computed by a single-valued WFA is subsequential iff it has bounded variation. Also, it is decidable in polynomial time whether a given WFA over the tropical semiring is single-valued.