Further Closure Properties of Input-Driven Pushdown Automata - Descriptional Complexity of Formal Systems
Conference Papers Year : 2018

Further Closure Properties of Input-Driven Pushdown Automata

Alexander Okhotin
  • Function : Author
  • PersonId : 1024589
Kai Salomaa
  • Function : Author
  • PersonId : 1022715

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.
Fichier principal
Vignette du fichier
470153_1_En_19_Chapter.pdf (387.71 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-01905626 , version 1 (26-10-2018)

Licence

Identifiers

Cite

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⟩
204 View
113 Download

Altmetric

Share

More