Standard

Descriptional complexity of unambiguous nested word automata. / Okhotin, Alexander; Salomaa, Kai.

Language and Automata Theory and Applications - 5th International Conference, LATA 2011, Proceedings. 2011. p. 414-426 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6638 LNCS).

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

Harvard

Okhotin, A & Salomaa, K 2011, Descriptional complexity of unambiguous nested word automata. in Language and Automata Theory and Applications - 5th International Conference, LATA 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6638 LNCS, pp. 414-426, 5th International Conference on Language and Automata Theory and Applications, LATA2011, Tarragona, Spain, 26/05/11. https://doi.org/10.1007/978-3-642-21254-3-33

APA

Okhotin, A., & Salomaa, K. (2011). Descriptional complexity of unambiguous nested word automata. In Language and Automata Theory and Applications - 5th International Conference, LATA 2011, Proceedings (pp. 414-426). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6638 LNCS). https://doi.org/10.1007/978-3-642-21254-3-33

Vancouver

Okhotin A, Salomaa K. Descriptional complexity of unambiguous nested word automata. In Language and Automata Theory and Applications - 5th International Conference, LATA 2011, Proceedings. 2011. p. 414-426. (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-21254-3-33

Author

Okhotin, Alexander ; Salomaa, Kai. / Descriptional complexity of unambiguous nested word automata. Language and Automata Theory and Applications - 5th International Conference, LATA 2011, Proceedings. 2011. pp. 414-426 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{f8d8ae73d06a4481b2468e3ac7f0e7af,
title = "Descriptional complexity of unambiguous nested word automata",
abstract = "It is known that converting an n-state nondeterministic nested word automaton (a.k.a. input-driven automaton; a.k.a. visibly pushdown automaton) to a corresponding deterministic automaton requires in the worst case 2 Θ(n2) states (R. Alur, P. Madhusudan: Adding nesting structure to words, DLT'06). We show that the same worst case 2Θ(n2) size blow-up occurs when converting a nondeterministic nested word automaton to an unambiguous one, and an unambiguous nested word automaton to a deterministic one. In addition, the methods developed in this paper are used to demonstrate that the state complexity of complementation for nondeterministic nested word automata is 2Θ(n2), and that the state complexity of homomorphism for deterministic nested word automata is 2Θ(n2).",
author = "Alexander Okhotin and Kai Salomaa",
year = "2011",
month = jun,
day = "8",
doi = "10.1007/978-3-642-21254-3-33",
language = "English",
isbn = "9783642212536",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "414--426",
booktitle = "Language and Automata Theory and Applications - 5th International Conference, LATA 2011, Proceedings",
note = "5th International Conference on Language and Automata Theory and Applications, LATA2011 ; Conference date: 26-05-2011 Through 31-05-2011",

}

RIS

TY - GEN

T1 - Descriptional complexity of unambiguous nested word automata

AU - Okhotin, Alexander

AU - Salomaa, Kai

PY - 2011/6/8

Y1 - 2011/6/8

N2 - It is known that converting an n-state nondeterministic nested word automaton (a.k.a. input-driven automaton; a.k.a. visibly pushdown automaton) to a corresponding deterministic automaton requires in the worst case 2 Θ(n2) states (R. Alur, P. Madhusudan: Adding nesting structure to words, DLT'06). We show that the same worst case 2Θ(n2) size blow-up occurs when converting a nondeterministic nested word automaton to an unambiguous one, and an unambiguous nested word automaton to a deterministic one. In addition, the methods developed in this paper are used to demonstrate that the state complexity of complementation for nondeterministic nested word automata is 2Θ(n2), and that the state complexity of homomorphism for deterministic nested word automata is 2Θ(n2).

AB - It is known that converting an n-state nondeterministic nested word automaton (a.k.a. input-driven automaton; a.k.a. visibly pushdown automaton) to a corresponding deterministic automaton requires in the worst case 2 Θ(n2) states (R. Alur, P. Madhusudan: Adding nesting structure to words, DLT'06). We show that the same worst case 2Θ(n2) size blow-up occurs when converting a nondeterministic nested word automaton to an unambiguous one, and an unambiguous nested word automaton to a deterministic one. In addition, the methods developed in this paper are used to demonstrate that the state complexity of complementation for nondeterministic nested word automata is 2Θ(n2), and that the state complexity of homomorphism for deterministic nested word automata is 2Θ(n2).

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

U2 - 10.1007/978-3-642-21254-3-33

DO - 10.1007/978-3-642-21254-3-33

M3 - Conference contribution

AN - SCOPUS:79957946511

SN - 9783642212536

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

SP - 414

EP - 426

BT - Language and Automata Theory and Applications - 5th International Conference, LATA 2011, Proceedings

T2 - 5th International Conference on Language and Automata Theory and Applications, LATA2011

Y2 - 26 May 2011 through 31 May 2011

ER -

ID: 41142776