Undecidability in Integer Weighted Finite Automata
Vesa Halava, Tero Harju · Fundamenta Informaticae · 1999
It is shown that the universe problem L(Aγ ) = A* is undecidable for 4-state finite automata A with integer weight function γ on its transitions. This holds even in the case, where A is acyclic and the weighting γ satisfies the unimodality condition.