How to travel between languages - Chatterjee, Krishnendu; Chaubal, Siddhesh; Rubin, Sasha; LATA: Conference on Language and Automata Theory and Applications; Modern Graph Algorithmic Techniques in Formal Verification; Game Theory; Quantitative Graph Games: Theory and Applications; Microsoft Research Faculty Fellowship (7th International Conference on Language and Automata Theory and Applications, 2013)
We consider how to edit strings from a source language so that the edited strings belong to a target language, where the languages are given as deterministic finite automata. Non-streaming (or offline) transducers perform edits given the whole source string. We show that the class of deterministic one-pass transducers with registers along with increment and min operation suffices for computing optimal edit distance, whereas the same class of transducers without the min operation is not sufficient. Streaming (or online) transducers perform edits as the letters of the source string are received. We present a polynomial time algorithm for the partial-repair problem that given a bound α asks for the construction of a deterministic streaming transducer (if one exists) that ensures that the ‘maximum fraction’ η of the strings of the source language are edited, within cost α, to the target language.
published
yes
Keywords: conference paper