---
res:
bibo_abstract:
- 'The edit distance between two words w 1 , w 2 is the minimal number of word operations
(letter insertions, deletions, and substitutions) necessary to transform w 1 to
w 2 . The edit distance generalizes to languages L 1 , L 2 , where the edit distance
from L 1 to L 2 is the minimal number k such that for every word from L 1 there
exists a word in L 2 with edit distance at most k . We study the edit distance
computation problem between pushdown automata and their subclasses. The 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 the following problems: (1) deciding whether, for a given threshold
k , the edit distance from a pushdown automaton to a finite automaton is at most
k , and (2) deciding whether the edit distance from a pushdown automaton to a
finite automaton is finite. @eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Thomas A
foaf_name: Henzinger, Thomas A
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87
orcid: 0000−0002−2985−7724
- foaf_Person:
foaf_givenName: Rasmus
foaf_name: Ibsen-Jensen, Rasmus
foaf_surname: Ibsen-Jensen
foaf_workInfoHomepage: http://www.librecat.org/personId=3B699956-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Jan
foaf_name: Otop, Jan
foaf_surname: Otop
bibo_doi: 10.23638/LMCS-13(3:23)2017
bibo_issue: '3'
bibo_volume: 13
dct_date: 2017^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/18605974
dct_language: eng
dct_publisher: International Federation of Computational Logic@
dct_title: Edit distance for pushdown automata@
...