Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Probabilistic Input-Driven Pushdown Automata. / Розе, Алексей Николаевич; Охотин, Александр Сергеевич.
48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France. Том 272 LIPIcs. ред. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. стр. 78:1-78:14 78 (Leibniz International Proceedings in Informatics, LIPIcs; Том 272).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
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
SP - 78:1-78:14
BT - 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 48th International Symposium on Mathematical Foundations of Computer Science
Y2 - 28 August 2023 through 1 September 2023
ER -
ID: 108696040