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.
repair regular languages asymptotic normalized cost edit distance distance automata