Standard

Probabilistic Input-Driven Pushdown Automata. / Розе, Алексей Николаевич; Охотин, Александр Сергеевич.

48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France. Vol. 272 LIPIcs. ed. Dagstuhl Publishing, 2023. 78 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 272).

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

Harvard

Розе, АН & Охотин, АС 2023, Probabilistic Input-Driven Pushdown Automata. in 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France. LIPIcs edn, vol. 272, 78, Leibniz International Proceedings in Informatics, LIPIcs, vol. 272, Dagstuhl Publishing, 48th International Symposium on Mathematical Foundations of Computer Science, Bordeaux, France, 28/08/23. https://doi.org/10.4230/LIPIcs.MFCS.2023.78

APA

Розе, А. Н., & Охотин, А. С. (2023). Probabilistic Input-Driven Pushdown Automata. In 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France (LIPIcs ed., Vol. 272). [78] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 272). Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.MFCS.2023.78

Vancouver

Розе АН, Охотин АС. Probabilistic Input-Driven Pushdown Automata. In 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France. LIPIcs ed. Vol. 272. Dagstuhl Publishing. 2023. 78. (Leibniz International Proceedings in Informatics, LIPIcs). https://doi.org/10.4230/LIPIcs.MFCS.2023.78

Author

Розе, Алексей Николаевич ; Охотин, Александр Сергеевич. / Probabilistic Input-Driven Pushdown Automata. 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France. Vol. 272 LIPIcs. ed. Dagstuhl Publishing, 2023. (Leibniz International Proceedings in Informatics, LIPIcs).

BibTeX

@inproceedings{a5113440559b46c2a66e1e1a2958f04f,
title = "Probabilistic Input-Driven Pushdown Automata",
abstract = "A probabilistic variant of input-driven pushdown automata (IDPDA), also known as visibly pushdown automata, is introduced. It is proved that these automata can be determinized: an n-state probabilistic IDPDA that accepts each string with probability at least λ + δ or at most λ − δ is transformed to a deterministic IDPDA with at most (1+ 1δ)n2−n states recognizing the same language. An asymptotically close lower bound is provided: for infinitely many n, there is a probabilistic IDPDA with 4n + 1 states and δ = 2701n, such that every equivalent deterministic IDPDA needs at least 7n2/14 states. A few special cases of automata with reduced determinization complexity are identified.",
keywords = "Finite automata, input-driven automata, probabilistic automata, state complexity, visibly pushdown automata",
author = "Розе, {Алексей Николаевич} and Охотин, {Александр Сергеевич}",
year = "2023",
month = aug,
doi = "10.4230/LIPIcs.MFCS.2023.78",
language = "English",
isbn = "978-3-95977-292-1",
volume = "272",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Dagstuhl Publishing",
booktitle = "48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France",
address = "Germany",
edition = "LIPIcs",
note = "48th International Symposium on Mathematical Foundations of Computer Science ; Conference date: 28-08-2023 Through 01-09-2023",
url = "https://mfcs2023.labri.fr",

}

RIS

TY - GEN

T1 - Probabilistic Input-Driven Pushdown Automata

AU - Розе, Алексей Николаевич

AU - Охотин, Александр Сергеевич

N1 - Conference code: 48

PY - 2023/8

Y1 - 2023/8

N2 - A probabilistic variant of input-driven pushdown automata (IDPDA), also known as visibly pushdown automata, is introduced. It is proved that these automata can be determinized: an n-state probabilistic IDPDA that accepts each string with probability at least λ + δ or at most λ − δ is transformed to a deterministic IDPDA with at most (1+ 1δ)n2−n states recognizing the same language. An asymptotically close lower bound is provided: for infinitely many n, there is a probabilistic IDPDA with 4n + 1 states and δ = 2701n, such that every equivalent deterministic IDPDA needs at least 7n2/14 states. A few special cases of automata with reduced determinization complexity are identified.

AB - A probabilistic variant of input-driven pushdown automata (IDPDA), also known as visibly pushdown automata, is introduced. It is proved that these automata can be determinized: an n-state probabilistic IDPDA that accepts each string with probability at least λ + δ or at most λ − δ is transformed to a deterministic IDPDA with at most (1+ 1δ)n2−n states recognizing the same language. An asymptotically close lower bound is provided: for infinitely many n, there is a probabilistic IDPDA with 4n + 1 states and δ = 2701n, such that every equivalent deterministic IDPDA needs at least 7n2/14 states. A few special cases of automata with reduced determinization complexity are identified.

KW - Finite automata

KW - input-driven automata

KW - probabilistic automata

KW - state complexity

KW - visibly pushdown automata

UR - https://www.mendeley.com/catalogue/190f9ac7-ad3c-3f31-ab9c-08018b85ffa6/

U2 - 10.4230/LIPIcs.MFCS.2023.78

DO - 10.4230/LIPIcs.MFCS.2023.78

M3 - Conference contribution

SN - 978-3-95977-292-1

VL - 272

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France

PB - Dagstuhl Publishing

T2 - 48th International Symposium on Mathematical Foundations of Computer Science

Y2 - 28 August 2023 through 1 September 2023

ER -

ID: 108696040