The per-character cost of repairing word languages

• We formalize the notion of asymptotic repair cost.
• We show how to compute the asymptotic repair cost between two regular languages.
• We give similar results in the streaming setting.

We show how to calculate the maximum number of edits per character needed to convert any string in one regular language to a string in another language. Our algorithm makes use of a local determinization procedure applicable to a subclass of distance automata. We then show how to calculate the same property when the editing needs to be done in streaming fashion, by a finite state transducer, using a reduction to mean-payoff games. In this case, we show that the optimal streaming editor can be produced in P.