%0 Conference Proceedings
%T Further Closure Properties of Input-Driven Pushdown Automata
%+ St Petersburg State University (SPbU)
%+ Queen's University [Kingston, Canada]
%A Okhotin, Alexander
%A Salomaa, Kai
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 20th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Halifax, NS, Canada
%Y Stavros Konstantinidis
%Y Giovanni Pighizzini
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-10952
%P 224-236
%8 2018-07-25
%D 2018
%R 10.1007/978-3-319-94631-3_19
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.2
%2 https://inria.hal.science/hal-01905626/document
%2 https://inria.hal.science/hal-01905626/file/470153_1_En_19_Chapter.pdf
%L hal-01905626
%U https://inria.hal.science/hal-01905626
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-10952