Edit distance l-neighborhood of a language L is the set of strings that can be obtained by at most l elementary edit operations— deleting or inserting one symbol in the string—from some string in L. We show that if L is recognized by a nondeterministic input-driven pushdown automaton (PDA) with ‖Γ‖ pushdown symbols and ‖Q‖ states, then its edit distance l-neighborhood can be recognized by a nondeterministic input-driven pda with 2⋅‖Γ‖+1 pushdown symbols and O(‖Q‖⋅l⋅‖Γ‖~l) states, which improves the known upper bound. We have obtained also a lower bound, namely, at least (‖Q‖ - 1)-‖Γ‖~l states are required. If the measure of edit distance includes also the operation of rewriting one symbol with another, the edit distance l-neighborhood can be recognized with 2⋅||Γ||+1 pushdown symbols and O(‖Q‖⋅l⋅‖Γ‖~(2⋅l)) states.
展开▼
