Further closure properties of input-driven pushdown automata

Alexander Okhotin, Kai Salomaa

Research output

1 Citation (Scopus)

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 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.

Original languageEnglish
Title of host publicationDescriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings
PublisherSpringer
Pages224-236
Number of pages13
ISBN (Print)9783319946306
DOIs
Publication statusPublished - 1 Jan 2018
Event20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018 - Halifax
Duration: 25 Jul 201827 Jul 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10952 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018
CountryCanada
CityHalifax
Period25/07/1827/07/18

    Fingerprint

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Okhotin, A., & Salomaa, K. (2018). Further closure properties of input-driven pushdown automata. In 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