# 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
Domain :

Cited literature [26 references]

https://hal.inria.fr/hal-01905626
Contributor : Hal Ifip <>
Submitted on : Friday, October 26, 2018 - 8:01:07 AM
Last modification on : Friday, October 26, 2018 - 8:05:09 AM
Long-term archiving on : Sunday, January 27, 2019 - 12:21:20 PM

### File

##### Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2021-01-01

### Citation

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