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 = {ω | ωω ∈ L}, and the first half 1/2L = {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 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.
展开▼
