Probabilistic input-driven pushdown automata

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 λ − δ, for some isolated cut-point λ ∈ [ 0, 1 ] with δ > 0, is transformed to a deterministic IDPDA recognizing the same language, with at most ( 1 + 1 δ ) n 2 − n states and at most | Σ + 1 | ⋅ ( 1 + 1 δ ) n 2 − n stack symbols, where Σ + 1 is the set of left bracket symbols in the alphabet. An asymptotically close lower bound is provided: for infinitely many n, there is a probabilistic IDPDA with 2 n + 3 states and n stack symbols, and with δ = 1 270 n, such that every equivalent deterministic IDPDA needs at least 7 n 2 / 14 states and at least n stack symbols. A few special cases of automata with reduced determinization complexity are identified.

Authors

• Alex Rose
• Alexander Okhotin

Keywords

• Finite automata
• Probabilistic automata
• Input-driven automata
• Visibly pushdown automata
• State complexity