Advertisement
Published in:
2013 | OriginalPaper | Chapter
How to Travel between Languages
Authors : Krishnendu Chatterjee, Siddhesh Chaubal, Sasha Rubin
Published in: Language and Automata Theory and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.