Limitedness theorem on finite automata with distance functions: An algebraic proof (Q807031)

A distance function on a finite automaton is a function assigning to each transition a nonnegative integer. To a sequence of transitions is then assigned the sum of the corresponding integers, and to a word w accepted by the automaton is assigned the number d(w) which is the minimum of all these integers corresponding to accepting paths for w. The problem of deciding whether d(w), w accepted, is bounded was solved by Hashiguchi. The author gives an algebraic proof of this result, by considering some exotic semiring introduced by Simon. Complexity results are also deduced: the author's algorithm is in \(2^{0(n^ 2)}\), with \(n=number\) of states, for the time, and PSPACE-hard.