TY - GEN

T1 - Further closure properties of input-driven pushdown automata

AU - Okhotin, Alexander

AU - Salomaa, Kai

PY - 2018/1/1

Y1 - 2018/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=85050607459&partnerID=8YFLogxK

UR - http://link.springer.com/10.1007/978-3-319-94631-3_19

UR - http://www.mendeley.com/research/further-closure-properties-inputdriven-pushdown-automata

U2 - 10.1007/978-3-319-94631-3_19

DO - 10.1007/978-3-319-94631-3_19

M3 - Conference contribution

AN - SCOPUS:85050607459

SN - 9783319946306

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

SP - 224

EP - 236

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

PB - Springer Nature

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

Y2 - 25 July 2018 through 27 July 2018

ER -