Standard

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

в: Theoretical Computer Science, Том 566, № C, 01.01.2015, стр. 1-11.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Harvard

Okhotin, A & Salomaa, K 2015, 'Descriptional complexity of unambiguous input-driven pushdown automata', Theoretical Computer Science, Том. 566, № C, стр. 1-11. https://doi.org/10.1016/j.tcs.2014.11.015

APA

Okhotin, A., & Salomaa, K. (2015). Descriptional complexity of unambiguous input-driven pushdown automata. Theoretical Computer Science, 566(C), 1-11. https://doi.org/10.1016/j.tcs.2014.11.015

Vancouver

Okhotin A, Salomaa K. Descriptional complexity of unambiguous input-driven pushdown automata. Theoretical Computer Science. 2015 Янв. 1;566(C):1-11. https://doi.org/10.1016/j.tcs.2014.11.015

Author

Okhotin, Alexander ; Salomaa, Kai. / Descriptional complexity of unambiguous input-driven pushdown automata. в: Theoretical Computer Science. 2015 ; Том 566, № C. стр. 1-11.

BibTeX

@article{cfde7010505b4479b559ed14650e8bfc,
title = "Descriptional complexity of unambiguous input-driven pushdown automata",
abstract = "It is known that a nondeterministic input-driven pushdown automaton (IDPDA) (a.k.a. visibly pushdown automaton; a.k.a. nested word automaton) with n states can be transformed to an equivalent deterministic automaton with 2Θ(n2) states (B. von Braunm{\"u}hl and R. Verbeek, 1983 [8]), and that this size is necessary in the worst case (R. Alur and P. Madhusudan, 2009 [4]). This paper demonstrates that the same worst-case 2Θ(n2) size blow-up occurs when converting a nondeterministic IDPDA to an unambiguous one, and an unambiguous IDPDA to a deterministic one. In addition, the methods developed in this paper are used to demonstrate that the descriptional complexity of complementation for nondeterministic IDPDAs is 2Θ(n2), and that the descriptional complexity of homomorphisms for deterministic IDPDAs is 2Θ(n2).",
keywords = "Descriptional complexity, Input-driven pushdown, Nested word automata, Nondeterminism, Unambiguity, Visibly pushdown automata",
author = "Alexander Okhotin and Kai Salomaa",
year = "2015",
month = jan,
day = "1",
doi = "10.1016/j.tcs.2014.11.015",
language = "English",
volume = "566",
pages = "1--11",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "C",

}

RIS

TY - JOUR

T1 - Descriptional complexity of unambiguous input-driven pushdown automata

AU - Okhotin, Alexander

AU - Salomaa, Kai

PY - 2015/1/1

Y1 - 2015/1/1

N2 - It is known that a nondeterministic input-driven pushdown automaton (IDPDA) (a.k.a. visibly pushdown automaton; a.k.a. nested word automaton) with n states can be transformed to an equivalent deterministic automaton with 2Θ(n2) states (B. von Braunmühl and R. Verbeek, 1983 [8]), and that this size is necessary in the worst case (R. Alur and P. Madhusudan, 2009 [4]). This paper demonstrates that the same worst-case 2Θ(n2) size blow-up occurs when converting a nondeterministic IDPDA to an unambiguous one, and an unambiguous IDPDA to a deterministic one. In addition, the methods developed in this paper are used to demonstrate that the descriptional complexity of complementation for nondeterministic IDPDAs is 2Θ(n2), and that the descriptional complexity of homomorphisms for deterministic IDPDAs is 2Θ(n2).

AB - It is known that a nondeterministic input-driven pushdown automaton (IDPDA) (a.k.a. visibly pushdown automaton; a.k.a. nested word automaton) with n states can be transformed to an equivalent deterministic automaton with 2Θ(n2) states (B. von Braunmühl and R. Verbeek, 1983 [8]), and that this size is necessary in the worst case (R. Alur and P. Madhusudan, 2009 [4]). This paper demonstrates that the same worst-case 2Θ(n2) size blow-up occurs when converting a nondeterministic IDPDA to an unambiguous one, and an unambiguous IDPDA to a deterministic one. In addition, the methods developed in this paper are used to demonstrate that the descriptional complexity of complementation for nondeterministic IDPDAs is 2Θ(n2), and that the descriptional complexity of homomorphisms for deterministic IDPDAs is 2Θ(n2).

KW - Descriptional complexity

KW - Input-driven pushdown

KW - Nested word automata

KW - Nondeterminism

KW - Unambiguity

KW - Visibly pushdown automata

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

U2 - 10.1016/j.tcs.2014.11.015

DO - 10.1016/j.tcs.2014.11.015

M3 - Article

AN - SCOPUS:84926390605

VL - 566

SP - 1

EP - 11

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - C

ER -

ID: 41140475