Edit distance for pushdown automata

Download
OA IST-2015-321-v1+1_main.pdf 279.07 KB [Published Version] OA IST-2018-955-v1+1_2017_Chatterjee_Edit_distance.pdf 279.07 KB

Journal Article | Published | English

Scopus indexed

Corresponding author has ISTA affiliation

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.
Publishing Year
Date Published
2017-09-13
Journal Title
Logical Methods in Computer Science
Publisher
International Federation of Computational Logic
Volume
13
Issue
3
ISSN
IST-REx-ID
465
All files available under the following license(s):
Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0):
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
08041379ba408d40664f449eb5907a8f
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
08041379ba408d40664f449eb5907a8f


Material in ISTA:
Earlier Version
Earlier Version

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar