STATE COMPLEXITY OF ADDITIVE WEIGHTED FINITE AUTOMATA
Kai Salomaa, Paul N. Schofield · International Journal of Foundations of Computer Science · 2007
It is known that the neighborhood of a regular language with respect to an additive distance is regular. We introduce an additive weighted finite automaton model that provides a conceptually simple way to reprove this result. We consider the state complexity of converting additive weighted finite automata to deterministic finite automata. As our main result we establish a tight upper bound for the state complexity of the conversion.