### 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}, the first half [Formula presented] and cyclic shift (Figure presented.). For K and L recognized by nondeterministic IDPDA, with m and with n states, respectively, insertion requires exactly mn+2m states, as long as K is well-nested; deletion requires exactly 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(n2)} states; the well-nested subset of the cyclic shift requires exactly 2n^{2} states. Without the well-nestedness constraints, non-closure is established in each case.

Original language | English |
---|---|

Pages (from-to) | 65-77 |

Journal | Theoretical Computer Science |

Volume | 798 |

Early online date | 20 May 2019 |

DOIs | |

Publication status | Published - 17 Dec 2019 |

### Fingerprint

### Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Theoretical Computer Science*,

*798*, 65-77. https://doi.org/10.1016/j.tcs.2019.04.006