Standard

Probabilistic input-driven pushdown automata. / Розе, Алексей Николаевич; Охотин, Александр Сергеевич.

In: Information and Computation, Vol. 305, 105312, 06.2025.

Research output: Contribution to journal › Article › peer-review

Harvard

Розе, АН & Охотин, АС 2025, 'Probabilistic input-driven pushdown automata', Information and Computation, vol. 305, 105312. https://doi.org/10.1016/j.ic.2025.105312

APA

Розе, А. Н., & Охотин, А. С. (2025). Probabilistic input-driven pushdown automata. Information and Computation, 305, [105312]. https://doi.org/10.1016/j.ic.2025.105312

Vancouver

Розе АН, Охотин АС. Probabilistic input-driven pushdown automata. Information and Computation. 2025 Jun;305. 105312. https://doi.org/10.1016/j.ic.2025.105312

Author

Розе, Алексей Николаевич ; Охотин, Александр Сергеевич. / Probabilistic input-driven pushdown automata. In: Information and Computation. 2025 ; Vol. 305.

BibTeX

@article{06d29cc99b23408e8647df7f7fc7c061,
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 λ−δ, for some isolated cut-point λ∈[0,1] with δ>0, is transformed to a deterministic IDPDA recognizing the same language, with at most (1+[Formula presented])n2−n states and at most |Σ+1|⋅(1+[Formula presented])n2−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 2n+3 states and n stack symbols, and with δ=[Formula presented], such that every equivalent deterministic IDPDA needs at least 7n2/14 states and at least n stack symbols. 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 = "2025",
month = jun,
doi = "10.1016/j.ic.2025.105312",
language = "English",
volume = "305",
journal = "Information and Computation",
issn = "0890-5401",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Probabilistic input-driven pushdown automata

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

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

PY - 2025/6

Y1 - 2025/6

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 λ−δ, for some isolated cut-point λ∈[0,1] with δ>0, is transformed to a deterministic IDPDA recognizing the same language, with at most (1+[Formula presented])n2−n states and at most |Σ+1|⋅(1+[Formula presented])n2−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 2n+3 states and n stack symbols, and with δ=[Formula presented], such that every equivalent deterministic IDPDA needs at least 7n2/14 states and at least n stack symbols. 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 λ−δ, for some isolated cut-point λ∈[0,1] with δ>0, is transformed to a deterministic IDPDA recognizing the same language, with at most (1+[Formula presented])n2−n states and at most |Σ+1|⋅(1+[Formula presented])n2−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 2n+3 states and n stack symbols, and with δ=[Formula presented], such that every equivalent deterministic IDPDA needs at least 7n2/14 states and at least n stack symbols. 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/15354502-e41a-3245-ae7e-ab151725b457/

U2 - 10.1016/j.ic.2025.105312

DO - 10.1016/j.ic.2025.105312

M3 - Article

VL - 305

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

M1 - 105312

ER -

ID: 135908624