2026-07-22T16:12:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18612 2024-03-06T11:02:16Z ddc:004 open_access

Probabilistic Input-Driven Pushdown Automata Rose, Alex Okhotin, Alexander Finite automata probabilistic automata input-driven automata visibly pushdown automata state complexity 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/δ)^(n² - 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 δ = 1/(270n), such that every equivalent deterministic IDPDA needs at least 7^(n²/14) states. A few special cases of automata with reduced determinization complexity are identified. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alex Rose and Alexander Okhotin 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.78 urn:nbn:de:0030-drops-186120 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.78 eng https://creativecommons.org/licenses/by/4.0/legalcode