### Abstract

The paper investigates the closure of the language family defined by input-driven pushdown automata (IDPDA) under the following operations: insertion (Formula presented), deletion (Formula presented), square root (Formula presented), and the first half (Formula presented). 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(n2)} states. Without the well-nestedness constraints, non-closure is established in each case.

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

Title of host publication | Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings |

Publisher | Springer |

Pages | 224-236 |

Number of pages | 13 |

ISBN (Print) | 9783319946306 |

DOIs | |

Publication status | Published - 1 Jan 2018 |

Event | 20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018 - Halifax Duration: 25 Jul 2018 → 27 Jul 2018 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 10952 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018 |
---|---|

Country | Canada |

City | Halifax |

Period | 25/07/18 → 27/07/18 |

### Fingerprint

### Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings*(pp. 224-236). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10952 LNCS). Springer. https://doi.org/10.1007/978-3-319-94631-3_19