Edit distance neighbourhoods of input-driven pushdown automata

Standard

Edit distance neighbourhoods of input-driven pushdown automata. / Okhotin, Alexander; Salomaa, Kai.

In: Theoretical Computer Science, Vol. 777, 19.07.2019, p. 417-430.

Research output: Contribution to journal › Article › peer-review

Author

Okhotin, Alexander ; Salomaa, Kai. / Edit distance neighbourhoods of input-driven pushdown automata. In: Theoretical Computer Science. 2019 ; Vol. 777. pp. 417-430.

BibTeX

@article{b247cd4da0404bf1892309ded01a1ac6,

title = "Edit distance neighbourhoods of input-driven pushdown automata",

abstract = "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.",

keywords = "Edit distance, Input-driven automata, State complexity, Visibly pushdown automata, STATE COMPLEXITY, LANGUAGES",

author = "Alexander Okhotin and Kai Salomaa",

year = "2019",

month = jul,

day = "19",

doi = "10.1016/j.tcs.2019.03.005",

language = "English",

volume = "777",

pages = "417--430",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Edit distance neighbourhoods of input-driven pushdown automata

AU - Okhotin, Alexander

AU - Salomaa, Kai

PY - 2019/7/19

Y1 - 2019/7/19

N2 - 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.

AB - 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.

KW - Edit distance

KW - Input-driven automata

KW - State complexity

KW - Visibly pushdown automata

KW - STATE COMPLEXITY

KW - LANGUAGES

UR - http://www.scopus.com/inward/record.url?scp=85062951701&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2019.03.005

DO - 10.1016/j.tcs.2019.03.005

M3 - Article

AN - SCOPUS:85062951701

VL - 777

SP - 417

EP - 430

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -

ID: 43676311