Weighted finite automata: the linear hull and the Pólya property

Weighted finite automata (WFAs), with coefficients in a semiring K, are a basic computational model that generalizes linear recurrence sequences to a (noncommutative) multivariate setting. A classical theorem of Schützenberger from the 60s characterizes their generating series as precisely the noncommutative rational series; from another perspective, many problems about weighted automata are related to understanding the dynamics of a vector under the action of a finitely generated matrix semigroup. After discussing the basic notions, I will restrict to the case where K is a field, illustrate a recent new invariant (the linear hull), and state a theorem that characterizes rational series generated by unambiguous, respectively, deterministic WFAs by an arithmetical property on their coefficients (the univariate case is already due to Pólya; the multivariate case resolves a conjecture of Reutenauer from the 70s). Together with a computability result on the (linear) Zariski closure of a finitely generated matrix semigroup, this shows the algorithmic decidability of the determinizability and the unambigualizability problems for WFAs with coefficients in a field. I will also discuss some related open problems.

(Joint work with J. Bell)