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)={xyzxzL,yK}

, deletion del(L,K)={xzxyzL,yK}
, square root L={wwwL}
, and the first half 12L={uv:|u|=|v|,uvL}
. 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 n3O(n2)
states, for well-nested L; the well-nested subset of the first half is representable with 2O(n2)
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) 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⟩
229 View
132 Download

Altmetric

Share

  • More