Skip to Main content Skip to Navigation
Conference papers

Further Closure Properties of Input-Driven Pushdown Automata

Abstract : The paper investigates the closure of the language family defined by input-driven pushdown automata (IDPDA) under the following operations: insertion $$ins(L, K)=\{xyz \mid xz \in L, \, y \in K\}$$, deletion $$del(L, K)=\{xz \mid xyz \in L, \, y \in K\}$$, square root $$\sqrt{L}=\{w \mid ww \in L\}$$, and the first half $$\frac{1}{2}L=\{u \mid \exists v: |u|=|v|, \, uv \in L\}$$. For K and L recognized by nondeterministic IDPDA, with m and with n states, respectively, insertion requires $$mn+2m$$ states, as long as K is well-nested; deletion is representable with 2n states, for well-nested K; square root requires $$n^3-O(n^2)$$ states, for well-nested L; the well-nested subset of the first half is representable with $$2^{O(n^2)}$$ states. Without the well-nestedness constraints, non-closure is established in each case.
Document type :
Conference papers
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Hal Ifip <>
Submitted on : Friday, October 26, 2018 - 8:01:07 AM
Last modification on : Monday, December 7, 2020 - 9:44:02 AM
Long-term archiving on: : Sunday, January 27, 2019 - 12:21:20 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Alexander Okhotin, Kai Salomaa. Further Closure Properties of Input-Driven Pushdown Automata. 20th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2018, Halifax, NS, Canada. pp.224-236, ⟨10.1007/978-3-319-94631-3_19⟩. ⟨hal-01905626⟩



Record views


Files downloads