New upper bounds to the limitedness of distance automata

A distance automaton is a finite nondeterministic automaton with a distance function which assigns zero or one to each atomic transition and assigns a nonnegative integer to each accepted word by the plus-min principle. In th is paper, we prove that the distances of all accepted words of a distance a utomaton is bounded by some constant if and only if they are bounded by 2(4 m3) (+ m Log(m+2)+m), where m is the number of states of the automaton. (C) 2000 Elsevier Science B.V. All rights reserved.