Undecidability in Integer Weighted Finite Automata

Abstract

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. The language L(A^γ) is defined as the set of words ω for which there exists a path π of A having zero weight, that is, γ(π) = 0.