---
_id: '5438'
abstract:
- lang: eng
  text: "The edit distance between two words w1, w2 is the minimal number of word
    operations (letter insertions, deletions, and substitutions) necessary to transform
    w1 to w2. The edit distance generalizes to languages L1, L2, where the edit distance
    is the minimal number k such that for every word from L1 there exists a word in
    L2 with edit distance at most k. We study the edit distance computation problem
    between pushdown automata and their subclasses.\r\nThe problem of computing edit
    distance to a pushdown automaton is undecidable, and in practice, the interesting
    question is to compute the edit distance from a pushdown automaton (the implementation,
    a standard model for programs with recursion) to a regular language (the specification).
    In this work, we present a complete picture of decidability and complexity for
    deciding whether, for a given threshold k, the edit distance from a pushdown automaton
    to a finite automaton is at most k. "
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Rasmus
  full_name: Ibsen-Jensen, Rasmus
  id: 3B699956-F248-11E8-B48F-1D18A9856A87
  last_name: Ibsen-Jensen
  orcid: 0000-0003-4783-0389
- first_name: Jan
  full_name: Otop, Jan
  id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
  last_name: Otop
citation:
  ama: Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. <i>Edit Distance for Pushdown
    Automata</i>. IST Austria; 2015. doi:<a href="https://doi.org/10.15479/AT:IST-2015-334-v1-1">10.15479/AT:IST-2015-334-v1-1</a>
  apa: Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., &#38; Otop, J. (2015).
    <i>Edit distance for pushdown automata</i>. IST Austria. <a href="https://doi.org/10.15479/AT:IST-2015-334-v1-1">https://doi.org/10.15479/AT:IST-2015-334-v1-1</a>
  chicago: Chatterjee, Krishnendu, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Jan
    Otop. <i>Edit Distance for Pushdown Automata</i>. IST Austria, 2015. <a href="https://doi.org/10.15479/AT:IST-2015-334-v1-1">https://doi.org/10.15479/AT:IST-2015-334-v1-1</a>.
  ieee: K. Chatterjee, T. A. Henzinger, R. Ibsen-Jensen, and J. Otop, <i>Edit distance
    for pushdown automata</i>. IST Austria, 2015.
  ista: Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for
    pushdown automata, IST Austria, 15p.
  mla: Chatterjee, Krishnendu, et al. <i>Edit Distance for Pushdown Automata</i>.
    IST Austria, 2015, doi:<a href="https://doi.org/10.15479/AT:IST-2015-334-v1-1">10.15479/AT:IST-2015-334-v1-1</a>.
  short: K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, Edit Distance for
    Pushdown Automata, IST Austria, 2015.
date_created: 2018-12-12T11:39:20Z
date_published: 2015-05-05T00:00:00Z
date_updated: 2026-07-06T13:27:53Z
day: '05'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-334-v1-1
file:
- access_level: open_access
  checksum: 8a5f2d77560e552af87eb1982437a43b
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T11:53:56Z
  date_updated: 2020-07-14T12:46:55Z
  file_id: '5518'
  file_name: IST-2015-334-v1+1_report.pdf
  file_size: 422573
  relation: main_file
file_date_updated: 2020-07-14T12:46:55Z
has_accepted_license: '1'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: '15'
publication_identifier:
  issn:
  - 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '334'
related_material:
  record:
  - id: '1610'
    relation: later_version
    status: public
  - id: '465'
    relation: later_version
    status: public
status: public
title: Edit distance for pushdown automata
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...