Edit distance neighbourhoods of input-driven pushdown automata

Alexander Okhotin, Kai Salomaa

Результат исследований: Научные публикации в периодических изданияхстатьярецензирование

3 Цитирования (Scopus)


Edit distance ℓ-neighbourhood of a formal language is the set of all strings that can be transformed to one of the strings in this language by at most ℓ insertions and deletions. Both the regular and the context-free languages are known to be closed under this operation, whereas the family recognized by deterministic pushdown automata is not. This paper establishes the closure of the family recognized by input-driven pushdown automata (IDPDA), also known as visibly pushdown automata, under the edit distance neighbourhood operation. For an n-state nondeterministic IDPDA with n stack symbols, an automaton for its edit distance ℓ-neighbourhood using O(nℓ+1) states is constructed, and an asymptotically matching lower bound is established. For an n-state deterministic IDPDA, its 1-neighbourhood in the worst case requires a deterministic IDPDA with at least 2Ω(n2) states.

Язык оригиналаанглийский
Страницы (с-по)417-430
Число страниц14
ЖурналTheoretical Computer Science
СостояниеОпубликовано - 19 июл 2019

Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

Fingerprint Подробные сведения о темах исследования «Edit distance neighbourhoods of input-driven pushdown automata». Вместе они формируют уникальный семантический отпечаток (fingerprint).