Standard

On the Determinization of Event-Clock Input-Driven Pushdown Automata. / Ogawa, Mizuhito; Okhotin, Alexander.

Computer Science – Theory and Applications - 17th International Computer Science Symposium in Russia, CSR 2022, Proceedings. ред. / Alexander S. Kulikov; Sofya Raskhodnikova. Springer Nature, 2022. стр. 256-268 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 13296 LNCS).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование

Harvard

Ogawa, M & Okhotin, A 2022, On the Determinization of Event-Clock Input-Driven Pushdown Automata. в AS Kulikov & S Raskhodnikova (ред.), Computer Science – Theory and Applications - 17th International Computer Science Symposium in Russia, CSR 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 13296 LNCS, Springer Nature, стр. 256-268, 17th International Computer Science Symposium in Russia, CSR 2022, Virtual, Online, 29/06/22. https://doi.org/10.1007/978-3-031-09574-0_16

APA

Ogawa, M., & Okhotin, A. (2022). On the Determinization of Event-Clock Input-Driven Pushdown Automata. в A. S. Kulikov, & S. Raskhodnikova (Ред.), Computer Science – Theory and Applications - 17th International Computer Science Symposium in Russia, CSR 2022, Proceedings (стр. 256-268). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 13296 LNCS). Springer Nature. https://doi.org/10.1007/978-3-031-09574-0_16

Vancouver

Ogawa M, Okhotin A. On the Determinization of Event-Clock Input-Driven Pushdown Automata. в Kulikov AS, Raskhodnikova S, Редакторы, Computer Science – Theory and Applications - 17th International Computer Science Symposium in Russia, CSR 2022, Proceedings. Springer Nature. 2022. стр. 256-268. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-031-09574-0_16

Author

Ogawa, Mizuhito ; Okhotin, Alexander. / On the Determinization of Event-Clock Input-Driven Pushdown Automata. Computer Science – Theory and Applications - 17th International Computer Science Symposium in Russia, CSR 2022, Proceedings. Редактор / Alexander S. Kulikov ; Sofya Raskhodnikova. Springer Nature, 2022. стр. 256-268 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{0210d0437a254899a5df00120242d0de,
title = "On the Determinization of Event-Clock Input-Driven Pushdown Automata",
abstract = "A timed extension of input-driven pushdown automata (also known as visibly pushdown automata and as nested word automata) under the event-clock model was introduced by Nguyen and Ogawa (“Event-clock visibly pushdown automata”, 2009), who showed that this model can be determinized using the method of region construction. This paper proposes a new, direct determinization procedure for these automata: an n-state nondeterministic automaton with k different clock constraints is transformed to a deterministic automaton with 2n2 states, 2n2+k stack symbols and the same clock constraints as in the original automaton. The construction is shown to be asymptotically optimal with respect to both the number of states and the number of stack symbols.",
keywords = "determinization, input-driven pushdown automata, state complexity, Timed systems, visibly pushdown automata",
author = "Mizuhito Ogawa and Alexander Okhotin",
note = "Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; 17th International Computer Science Symposium in Russia, CSR 2022 ; Conference date: 29-06-2022 Through 01-07-2022",
year = "2022",
month = jun,
doi = "10.1007/978-3-031-09574-0_16",
language = "English",
isbn = "9783031095733",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "256--268",
editor = "Kulikov, {Alexander S.} and Sofya Raskhodnikova",
booktitle = "Computer Science – Theory and Applications - 17th International Computer Science Symposium in Russia, CSR 2022, Proceedings",
address = "Germany",

}

RIS

TY - GEN

T1 - On the Determinization of Event-Clock Input-Driven Pushdown Automata

AU - Ogawa, Mizuhito

AU - Okhotin, Alexander

N1 - Publisher Copyright: © 2022, Springer Nature Switzerland AG.

PY - 2022/6

Y1 - 2022/6

N2 - A timed extension of input-driven pushdown automata (also known as visibly pushdown automata and as nested word automata) under the event-clock model was introduced by Nguyen and Ogawa (“Event-clock visibly pushdown automata”, 2009), who showed that this model can be determinized using the method of region construction. This paper proposes a new, direct determinization procedure for these automata: an n-state nondeterministic automaton with k different clock constraints is transformed to a deterministic automaton with 2n2 states, 2n2+k stack symbols and the same clock constraints as in the original automaton. The construction is shown to be asymptotically optimal with respect to both the number of states and the number of stack symbols.

AB - A timed extension of input-driven pushdown automata (also known as visibly pushdown automata and as nested word automata) under the event-clock model was introduced by Nguyen and Ogawa (“Event-clock visibly pushdown automata”, 2009), who showed that this model can be determinized using the method of region construction. This paper proposes a new, direct determinization procedure for these automata: an n-state nondeterministic automaton with k different clock constraints is transformed to a deterministic automaton with 2n2 states, 2n2+k stack symbols and the same clock constraints as in the original automaton. The construction is shown to be asymptotically optimal with respect to both the number of states and the number of stack symbols.

KW - determinization

KW - input-driven pushdown automata

KW - state complexity

KW - Timed systems

KW - visibly pushdown automata

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

UR - https://www.mendeley.com/catalogue/94ef9108-4ea2-39af-9f85-14d13290e2a4/

U2 - 10.1007/978-3-031-09574-0_16

DO - 10.1007/978-3-031-09574-0_16

M3 - Conference contribution

AN - SCOPUS:85134165668

SN - 9783031095733

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

SP - 256

EP - 268

BT - Computer Science – Theory and Applications - 17th International Computer Science Symposium in Russia, CSR 2022, Proceedings

A2 - Kulikov, Alexander S.

A2 - Raskhodnikova, Sofya

PB - Springer Nature

T2 - 17th International Computer Science Symposium in Russia, CSR 2022

Y2 - 29 June 2022 through 1 July 2022

ER -

ID: 97267370