Standard

Descriptional complexity of input-driven pushdown automata. / Okhotin, Alexander; Piao, Xiaoxue; Salomaa, Kai.

Languages Alive: Essays Dedicated to Jurgen Dassow on the Occasion of His 65th Birthday. ed. / Henning Bordihn; Martin Kutrib; Bianca Truthe. 2012. p. 186-206 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7300 LNAI).

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

Harvard

Okhotin, A, Piao, X & Salomaa, K 2012, Descriptional complexity of input-driven pushdown automata. in H Bordihn, M Kutrib & B Truthe (eds), Languages Alive: Essays Dedicated to Jurgen Dassow on the Occasion of His 65th Birthday. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7300 LNAI, pp. 186-206. https://doi.org/10.1007/978-3-642-31644-9-13

APA

Okhotin, A., Piao, X., & Salomaa, K. (2012). Descriptional complexity of input-driven pushdown automata. In H. Bordihn, M. Kutrib, & B. Truthe (Eds.), Languages Alive: Essays Dedicated to Jurgen Dassow on the Occasion of His 65th Birthday (pp. 186-206). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7300 LNAI). https://doi.org/10.1007/978-3-642-31644-9-13

Vancouver

Okhotin A, Piao X, Salomaa K. Descriptional complexity of input-driven pushdown automata. In Bordihn H, Kutrib M, Truthe B, editors, Languages Alive: Essays Dedicated to Jurgen Dassow on the Occasion of His 65th Birthday. 2012. p. 186-206. (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-31644-9-13

Author

Okhotin, Alexander ; Piao, Xiaoxue ; Salomaa, Kai. / Descriptional complexity of input-driven pushdown automata. Languages Alive: Essays Dedicated to Jurgen Dassow on the Occasion of His 65th Birthday. editor / Henning Bordihn ; Martin Kutrib ; Bianca Truthe. 2012. pp. 186-206 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inbook{c5a18f04f0544a9a999d7bc9a9a44c22,
title = "Descriptional complexity of input-driven pushdown automata",
abstract = "It is known that a nondeterministic input-driven pushdown automaton (IDPDA) can be determinized. Alur and Madhusudan (Adding nesting structure to words, J.ACM 56(3), 2009) showed that a deterministic IDPDA simulating a nondeterministic IDPDA with n states and stack symbols may need, in the worst case, states. In their construction, the equivalent deterministic IDPDA does, in fact, not need to use the stack. This paper considers the size blow-up of determinization in more detail, and gives a lower bound construction, that is tight within a multiplicative constant, with respect to the size of the nondeterministic automaton both for the number of states and the number of stack symbols. The paper also surveys the recent results on operational state complexity of IDPDAs, and on the cost of converting a nondeterministic automaton to an unambiguous one, and an unambiguous automaton to a deterministic one.",
keywords = "descriptional complexity, input-driven pushdown, nondeterminism, state complexity",
author = "Alexander Okhotin and Xiaoxue Piao and Kai Salomaa",
year = "2012",
month = oct,
day = "8",
doi = "10.1007/978-3-642-31644-9-13",
language = "English",
isbn = "9783642316432",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "186--206",
editor = "Henning Bordihn and Martin Kutrib and Bianca Truthe",
booktitle = "Languages Alive",

}

RIS

TY - CHAP

T1 - Descriptional complexity of input-driven pushdown automata

AU - Okhotin, Alexander

AU - Piao, Xiaoxue

AU - Salomaa, Kai

PY - 2012/10/8

Y1 - 2012/10/8

N2 - It is known that a nondeterministic input-driven pushdown automaton (IDPDA) can be determinized. Alur and Madhusudan (Adding nesting structure to words, J.ACM 56(3), 2009) showed that a deterministic IDPDA simulating a nondeterministic IDPDA with n states and stack symbols may need, in the worst case, states. In their construction, the equivalent deterministic IDPDA does, in fact, not need to use the stack. This paper considers the size blow-up of determinization in more detail, and gives a lower bound construction, that is tight within a multiplicative constant, with respect to the size of the nondeterministic automaton both for the number of states and the number of stack symbols. The paper also surveys the recent results on operational state complexity of IDPDAs, and on the cost of converting a nondeterministic automaton to an unambiguous one, and an unambiguous automaton to a deterministic one.

AB - It is known that a nondeterministic input-driven pushdown automaton (IDPDA) can be determinized. Alur and Madhusudan (Adding nesting structure to words, J.ACM 56(3), 2009) showed that a deterministic IDPDA simulating a nondeterministic IDPDA with n states and stack symbols may need, in the worst case, states. In their construction, the equivalent deterministic IDPDA does, in fact, not need to use the stack. This paper considers the size blow-up of determinization in more detail, and gives a lower bound construction, that is tight within a multiplicative constant, with respect to the size of the nondeterministic automaton both for the number of states and the number of stack symbols. The paper also surveys the recent results on operational state complexity of IDPDAs, and on the cost of converting a nondeterministic automaton to an unambiguous one, and an unambiguous automaton to a deterministic one.

KW - descriptional complexity

KW - input-driven pushdown

KW - nondeterminism

KW - state complexity

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

U2 - 10.1007/978-3-642-31644-9-13

DO - 10.1007/978-3-642-31644-9-13

M3 - Chapter

AN - SCOPUS:84867012117

SN - 9783642316432

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

SP - 186

EP - 206

BT - Languages Alive

A2 - Bordihn, Henning

A2 - Kutrib, Martin

A2 - Truthe, Bianca

ER -

ID: 41140066