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∣xz∈L,y∈K}
, deletion del(L,K)={xz∣xyz∈L,y∈K}
, square root √L={w∣ww∈L}
, and the first half 12L={u∣∃v:|u|=|v|,uv∈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 n3−O(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.
Domains
Origin | Files produced by the author(s) |
---|
Loading...