Standard

Input-Driven Pushdown Automata on Well-Nested Infinite Strings. / Okhotin, Alexander; Selivanov, Victor L.

Computer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings. ed. / Rahul Santhanam; Daniil Musatov. Springer Nature, 2021. p. 349-360 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12730 LNCS).

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

Harvard

Okhotin, A & Selivanov, VL 2021, Input-Driven Pushdown Automata on Well-Nested Infinite Strings. in R Santhanam & D Musatov (eds), Computer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12730 LNCS, Springer Nature, pp. 349-360, 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russian Federation, 28/06/21. https://doi.org/10.1007/978-3-030-79416-3_21

APA

Okhotin, A., & Selivanov, V. L. (2021). Input-Driven Pushdown Automata on Well-Nested Infinite Strings. In R. Santhanam, & D. Musatov (Eds.), Computer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings (pp. 349-360). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12730 LNCS). Springer Nature. https://doi.org/10.1007/978-3-030-79416-3_21

Vancouver

Okhotin A, Selivanov VL. Input-Driven Pushdown Automata on Well-Nested Infinite Strings. In Santhanam R, Musatov D, editors, Computer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings. Springer Nature. 2021. p. 349-360. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-79416-3_21

Author

Okhotin, Alexander ; Selivanov, Victor L. / Input-Driven Pushdown Automata on Well-Nested Infinite Strings. Computer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings. editor / Rahul Santhanam ; Daniil Musatov. Springer Nature, 2021. pp. 349-360 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{85473609da214e73b599c6c3be46de21,
title = "Input-Driven Pushdown Automata on Well-Nested Infinite Strings",
abstract = "Automata operating on strings of nested brackets, known as input-driven pushdown automata, and also as visibly pushdown automata, have been studied since the 1980s. They were extended to the case of infinite strings by Alur and Madhusudan (“Visibly pushdown languages”, STOC 2004). This paper investigates the properties of these automata under the assumption that a given infinite string is always well-nested. This restriction enables a complete characterization of the corresponding ω -languages in terms of classical ω -regular languages and input-driven pushdown automata on finite strings. This characterization leads to a determinization construction for these automata, as well as to the first results on their topological classification.",
author = "Alexander Okhotin and Selivanov, {Victor L.}",
note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 16th International Computer Science Symposium in Russia, CSR 2021 ; Conference date: 28-06-2021 Through 02-07-2021",
year = "2021",
month = jun,
doi = "10.1007/978-3-030-79416-3_21",
language = "English",
isbn = "9783030794156",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "349--360",
editor = "Rahul Santhanam and Daniil Musatov",
booktitle = "Computer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings",
address = "Germany",

}

RIS

TY - GEN

T1 - Input-Driven Pushdown Automata on Well-Nested Infinite Strings

AU - Okhotin, Alexander

AU - Selivanov, Victor L.

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

PY - 2021/6

Y1 - 2021/6

N2 - Automata operating on strings of nested brackets, known as input-driven pushdown automata, and also as visibly pushdown automata, have been studied since the 1980s. They were extended to the case of infinite strings by Alur and Madhusudan (“Visibly pushdown languages”, STOC 2004). This paper investigates the properties of these automata under the assumption that a given infinite string is always well-nested. This restriction enables a complete characterization of the corresponding ω -languages in terms of classical ω -regular languages and input-driven pushdown automata on finite strings. This characterization leads to a determinization construction for these automata, as well as to the first results on their topological classification.

AB - Automata operating on strings of nested brackets, known as input-driven pushdown automata, and also as visibly pushdown automata, have been studied since the 1980s. They were extended to the case of infinite strings by Alur and Madhusudan (“Visibly pushdown languages”, STOC 2004). This paper investigates the properties of these automata under the assumption that a given infinite string is always well-nested. This restriction enables a complete characterization of the corresponding ω -languages in terms of classical ω -regular languages and input-driven pushdown automata on finite strings. This characterization leads to a determinization construction for these automata, as well as to the first results on their topological classification.

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

UR - https://www.mendeley.com/catalogue/6d6265dc-c31c-35ec-a120-ce29294f8448/

U2 - 10.1007/978-3-030-79416-3_21

DO - 10.1007/978-3-030-79416-3_21

M3 - Conference contribution

AN - SCOPUS:85111807385

SN - 9783030794156

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

SP - 349

EP - 360

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

A2 - Santhanam, Rahul

A2 - Musatov, Daniil

PB - Springer Nature

T2 - 16th International Computer Science Symposium in Russia, CSR 2021

Y2 - 28 June 2021 through 2 July 2021

ER -

ID: 84641633