Standard

State complexity of operations on input-driven pushdown automata. / Okhotin, Alexander; Salomaa, Kai.

Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Proceedings. 2011. p. 485-496 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6907 LNCS).

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

Harvard

Okhotin, A & Salomaa, K 2011, State complexity of operations on input-driven pushdown automata. in Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6907 LNCS, pp. 485-496, 36th International Symposium on Mathematical Foundations of Computer Science, MFCS 2011, Warsaw, Poland, 22/08/11. https://doi.org/10.1007/978-3-642-22993-0_44

APA

Okhotin, A., & Salomaa, K. (2011). State complexity of operations on input-driven pushdown automata. In Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Proceedings (pp. 485-496). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6907 LNCS). https://doi.org/10.1007/978-3-642-22993-0_44

Vancouver

Okhotin A, Salomaa K. State complexity of operations on input-driven pushdown automata. In Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Proceedings. 2011. p. 485-496. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-22993-0_44

Author

Okhotin, Alexander ; Salomaa, Kai. / State complexity of operations on input-driven pushdown automata. Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Proceedings. 2011. pp. 485-496 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{75a06c63c70a45399ef316e365d96910,
title = "State complexity of operations on input-driven pushdown automata",
abstract = "The family of deterministic input-driven pushdown automata (IDPDA; a.k.a. visibly pushdown automata, a.k.a. nested word automata) is known to be closed under reversal, concatenation and Kleene star. As shown by Alur and Madhusudan ({"}Visibly pushdown languages{"}, STOC 2004), the reversal and the Kleene star of an n-state IDPDA can be represented by an IDPDA 2O(n2) with states, while concatenation of an m-state and an n-state IDPDA is represented by an IDPDA with 2O((m+n)2) states. This paper presents more efficient constructions for the reversal and for the Kleene star, which yield 2 Θ(n log n) states, as well as an m 2 Θ(n log n)-state construction for the concatenation. These constructions are optimal due to the previously known matching lower bounds.",
author = "Alexander Okhotin and Kai Salomaa",
year = "2011",
doi = "10.1007/978-3-642-22993-0_44",
language = "English",
isbn = "9783642229923",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "485--496",
booktitle = "Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Proceedings",
note = "36th International Symposium on Mathematical Foundations of Computer Science, MFCS 2011 ; Conference date: 22-08-2011 Through 26-08-2011",

}

RIS

TY - GEN

T1 - State complexity of operations on input-driven pushdown automata

AU - Okhotin, Alexander

AU - Salomaa, Kai

PY - 2011

Y1 - 2011

N2 - The family of deterministic input-driven pushdown automata (IDPDA; a.k.a. visibly pushdown automata, a.k.a. nested word automata) is known to be closed under reversal, concatenation and Kleene star. As shown by Alur and Madhusudan ("Visibly pushdown languages", STOC 2004), the reversal and the Kleene star of an n-state IDPDA can be represented by an IDPDA 2O(n2) with states, while concatenation of an m-state and an n-state IDPDA is represented by an IDPDA with 2O((m+n)2) states. This paper presents more efficient constructions for the reversal and for the Kleene star, which yield 2 Θ(n log n) states, as well as an m 2 Θ(n log n)-state construction for the concatenation. These constructions are optimal due to the previously known matching lower bounds.

AB - The family of deterministic input-driven pushdown automata (IDPDA; a.k.a. visibly pushdown automata, a.k.a. nested word automata) is known to be closed under reversal, concatenation and Kleene star. As shown by Alur and Madhusudan ("Visibly pushdown languages", STOC 2004), the reversal and the Kleene star of an n-state IDPDA can be represented by an IDPDA 2O(n2) with states, while concatenation of an m-state and an n-state IDPDA is represented by an IDPDA with 2O((m+n)2) states. This paper presents more efficient constructions for the reversal and for the Kleene star, which yield 2 Θ(n log n) states, as well as an m 2 Θ(n log n)-state construction for the concatenation. These constructions are optimal due to the previously known matching lower bounds.

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

U2 - 10.1007/978-3-642-22993-0_44

DO - 10.1007/978-3-642-22993-0_44

M3 - Conference contribution

AN - SCOPUS:80052108418

SN - 9783642229923

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

SP - 485

EP - 496

BT - Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Proceedings

T2 - 36th International Symposium on Mathematical Foundations of Computer Science, MFCS 2011

Y2 - 22 August 2011 through 26 August 2011

ER -

ID: 78945375