Edit distance for pushdown automata
Download


Journal Article
| Published
| English
Scopus indexed
Author
Corresponding author has ISTA affiliation
Department
Grant
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
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
IST-2015-321-v1+1_main.pdf
279.07 KB
Access Level

Date Uploaded
2018-12-12
MD5 Checksum
08041379ba408d40664f449eb5907a8f
File Name
Access Level

Date Uploaded
2018-12-12
MD5 Checksum
08041379ba408d40664f449eb5907a8f
Material in ISTA:
Earlier Version
Earlier Version