Standard

Further closure properties of input-driven pushdown automata. / Okhotin, Alexander; Salomaa, Kai.

Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings. Springer Nature, 2018. p. 224-236 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10952 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10952 LNCS, Springer Nature, pp. 224-236, 20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018, Halifax, Canada, 25/07/18. https://doi.org/10.1007/978-3-319-94631-3_19

APA

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 Nature. https://doi.org/10.1007/978-3-319-94631-3_19

Vancouver

Okhotin A, Salomaa K. Further closure properties of input-driven pushdown automata. In Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings. Springer Nature. 2018. p. 224-236. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-94631-3_19

Author

Okhotin, Alexander ; Salomaa, Kai. / Further closure properties of input-driven pushdown automata. Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings. Springer Nature, 2018. pp. 224-236 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{85ab5b741b5b4839997ef2be7dd9d31d,
title = "Further closure properties of input-driven pushdown automata",
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.",
author = "Alexander Okhotin and Kai Salomaa",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-319-94631-3_19",
language = "English",
isbn = "9783319946306",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "224--236",
booktitle = "Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings",
address = "Germany",
note = "20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018 ; Conference date: 25-07-2018 Through 27-07-2018",

}

RIS

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 -

ID: 33857063