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.