Determinisability of unary weighted automata over the rational numbers
The contribution shows that the sequentiality problem for unary weighted finite automata (WFA) over the rational numbers is decidable and that an equivalent sequential WFA can effectively be constructed in the positive case. A weighted finite automaton is essentially a finite-state automaton in which each transition additionally carries a weight. The weights are rational numbers in this contribution and are multiplied along the several transitions that constitute a run, and the weights of multiple runs for the same input are added up. The sequentiality problem asks for a given WFA whether there exists an equivalent sequential (or deterministic) WFA in which for each state and input symbol there exists a unique (nonzero-weighted) transition. Finally, the WFA is unary if the input alphabet has at most one symbol. The sequentiality problem was only solved in very special cases for unary WFA. The author develops the notion of the characteristic polynomial for a given WFA. It is derivable from a minimal WFA for the same computed mapping. Such a minimal WFA can efficiently be derived easily using existing algorithms. It is demonstrated that the characteristic polynomial is invariant under changes of the basis, so the characteristic polynomial is actually unique for the computed function (and independent of the chosen minimal WFA computing it). It is demonstrated that the characteristic polynomial needs to have one of two special shapes for the given WFA to be determinizable. Essentially, the characteristic polynomial needs to be factorized and all its nonzero roots need to be simple. If the decision algorithm returns that the WFA is determinizable then an equivalent deterministic WFA can be determined efficiently as well. The contribution includes a detailed complexity analysis and several examples illustrate the decision as well as the construction algorithms. Overall, the paper is excellently written and provides exactly the right amount of detail and intuition. The examples help the reader to understand the approach, and the full proof details (and the exposition of the minimization algorithm) make the paper self-contained. Each computer science graduate with some background in automata theory and linear algebra should be able to fully appreciate this contribution.
scientific article; zbMATH DE number 7437228
scientific article