The per-character cost of repairing word languagesRevista : Theoretical Computer Science
Volumen : 539
Páginas : 38 - 67
Tipo de publicación : ISI Ir a publicación
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.