---
_id: '10902'
abstract:
- lang: eng
  text: 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.
acknowledgement: 'The research was supported by Austrian Science Fund (FWF) Grant
  No P 23499-N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph
  Games), and Microsoft faculty fellows award. Thanks to Gabriele Puppis for suggesting
  the problem of identifying a deterministic transducer to compute the optimal cost,
  and to Martin Chmelik for his comments on the introduction.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Siddhesh
  full_name: Chaubal, Siddhesh
  last_name: Chaubal
- first_name: Sasha
  full_name: Rubin, Sasha
  id: 2EC51194-F248-11E8-B48F-1D18A9856A87
  last_name: Rubin
citation:
  ama: 'Chatterjee K, Chaubal S, Rubin S. How to travel between languages. In: <i>7th
    International Conference on Language and Automata Theory and Applications</i>.
    Vol 7810. LNCS. Berlin, Heidelberg: Springer Nature; 2013:214-225. doi:<a href="https://doi.org/10.1007/978-3-642-37064-9_20">10.1007/978-3-642-37064-9_20</a>'
  apa: 'Chatterjee, K., Chaubal, S., &#38; Rubin, S. (2013). How to travel between
    languages. In <i>7th International Conference on Language and Automata Theory
    and Applications</i> (Vol. 7810, pp. 214–225). Berlin, Heidelberg: Springer Nature.
    <a href="https://doi.org/10.1007/978-3-642-37064-9_20">https://doi.org/10.1007/978-3-642-37064-9_20</a>'
  chicago: 'Chatterjee, Krishnendu, Siddhesh Chaubal, and Sasha Rubin. “How to Travel
    between Languages.” In <i>7th International Conference on Language and Automata
    Theory and Applications</i>, 7810:214–25. LNCS. Berlin, Heidelberg: Springer Nature,
    2013. <a href="https://doi.org/10.1007/978-3-642-37064-9_20">https://doi.org/10.1007/978-3-642-37064-9_20</a>.'
  ieee: K. Chatterjee, S. Chaubal, and S. Rubin, “How to travel between languages,”
    in <i>7th International Conference on Language and Automata Theory and Applications</i>,
    Bilbao, Spain, 2013, vol. 7810, pp. 214–225.
  ista: 'Chatterjee K, Chaubal S, Rubin S. 2013. How to travel between languages.
    7th International Conference on Language and Automata Theory and Applications.
    LATA: Conference on Language and Automata Theory and ApplicationsLNCS, LNCS, vol.
    7810, 214–225.'
  mla: Chatterjee, Krishnendu, et al. “How to Travel between Languages.” <i>7th International
    Conference on Language and Automata Theory and Applications</i>, vol. 7810, Springer
    Nature, 2013, pp. 214–25, doi:<a href="https://doi.org/10.1007/978-3-642-37064-9_20">10.1007/978-3-642-37064-9_20</a>.
  short: K. Chatterjee, S. Chaubal, S. Rubin, in:, 7th International Conference on
    Language and Automata Theory and Applications, Springer Nature, Berlin, Heidelberg,
    2013, pp. 214–225.
conference:
  end_date: 2013-04-05
  location: Bilbao, Spain
  name: 'LATA: Conference on Language and Automata Theory and Applications'
  start_date: 2013-04-02
date_created: 2022-03-21T07:56:21Z
date_published: 2013-04-15T00:00:00Z
date_updated: 2023-09-05T15:10:38Z
day: '15'
department:
- _id: KrCh
doi: 10.1007/978-3-642-37064-9_20
ec_funded: 1
intvolume: '      7810'
language:
- iso: eng
month: '04'
oa_version: None
page: 214-225
place: Berlin, Heidelberg
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P 23499-N23
  name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
  name: Microsoft Research Faculty Fellowship
publication: 7th International Conference on Language and Automata Theory and Applications
publication_identifier:
  eisbn:
  - '9783642370649'
  eissn:
  - 1611-3349
  isbn:
  - '9783642370632'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: How to travel between languages
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 7810
year: '2013'
...