×

zbMATH — the first resource for mathematics

Input-driven pushdown automata for edit distance neighborhood. (English) Zbl 07117540
Hofman, Piotrek (ed.) et al., Developments in language theory. 23rd international conference, DLT 2019, Warsaw, Poland, August 5–9, 2019. Proceedings. Cham: Springer (ISBN 978-3-030-24885-7/pbk; 978-3-030-24886-4/ebook). Lecture Notes in Computer Science 11647, 113-126 (2019).
Summary: Edit distance \(\ell\)-neighborhood of a language \(\mathcal{L}\) is the set of strings that can be obtained by at most \(\ell\) elementary edit operations – deleting or inserting one symbol in the string – from some string in \(\mathcal{L}\). We show that if \(\mathcal{L}\) is recognized by a nondeterministic input-driven pushdown automaton (pda) with \(\Vert{\Gamma}\Vert\) pushdown symbols and \(\Vert{Q}\Vert\) states, then its edit distance \(\ell\)-neighborhood can be recognized by a nondeterministic input-driven pda with \(2{\cdot }\Vert{\Gamma}\Vert{+}1\) pushdown symbols and \(\mathcal{O}(\Vert{Q}\Vert{\cdot}\ell{\cdot}\Vert{\Gamma}\Vert^{\ell})\) states, which improves the known upper bound. We have obtained also a lower bound, namely, at least \((\Vert{Q}\Vert{-}1){\cdot}\Vert{\Gamma}\Vert^{\ell}\) states are required. If the measure of edit distance includes also the operation of rewriting one symbol with another, the edit distance \(\ell\)-neighborhood can be recognized with \(2{\cdot}\Vert{\Gamma}\Vert{+}1\) pushdown symbols and \(\mathcal{O}(\Vert{Q}\Vert{\cdot }\ell{\cdot}\Vert{\Gamma}\Vert ^{2\cdot\ell})\) states.
For the entire collection see [Zbl 1416.68011].
MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI