https://hal.inria.fr/hal-01905626Okhotin, AlexanderAlexanderOkhotinSPbU - St Petersburg State UniversitySalomaa, KaiKaiSalomaaQueen's University [Kingston, Canada]Further Closure Properties of Input-Driven Pushdown AutomataHAL CCSD2018[INFO] Computer Science [cs]Ifip, HalStavros KonstantinidisGiovanni Pighizzini2018-10-26 08:01:072020-12-07 09:44:022018-10-26 08:05:09enConference papershttps://hal.inria.fr/hal-01905626/document10.1007/978-3-319-94631-3_19application/pdf1The 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.