一句话：按歧义度与字母表大小刻画一元/二元概率自动机空性和λ-可达性的复杂度。
本文研究一元和二元概率有限自动机（PFA）的空性与 λ-可达性问题，并按其歧义度及字母表大小刻画复杂度。主要结果表明：对于多项式歧义的一元 PFA，空性与 λ-可达性可在 EXPTIME 内求解；若转移矩阵为二元矩阵，则二者属于 NP。与指数歧义一元 PFA 的 Skolem 困难性形成对比，作者证明即使对有限歧义的一元 PFA，这两个问题也是 NP 难的。对于具有固定且可交换转移矩阵的二元多项式歧义 PFA，论文进一步证明 λ-可达性（维数 9）、非严格空性（维数 37）和严格空性（维数 40）的 NP 困难性。
We study the emptiness and $\lambda$-reachability problems for unary and binary Probabilistic Finite Automata (PFA) and characterise the complexity of these problems in terms of the degree of ambiguity of the automaton and the size of its alphabet. Our main result is that emptiness and $\lambda$-reachability are solvable in EXPTIME for polynomially ambiguous unary PFA and if, in addition, the transition matrix is binary, we show they are in NP. In contrast to the Skolem-hardness of the $\lambda$-reachability and emptiness problems for exponentially ambiguous unary PFA, we show that these problems are NP-hard even for finitely ambiguous unary PFA. For binary polynomially ambiguous PFA with fixed and commuting transition matrices, we prove NP-hardness of the $\lambda$-reachability (dimension 9), nonstrict emptiness (dimension 37) and strict emptiness (dimension 40) problems.
@article{paperbot2158,
title = {Decision Questions for Probabilistic Automata on Small Alphabets},
author = {Paul C. Bell and Pavel Semukhin},
journal = {Logical Methods in Computer Science},
volume = {Volume 19, Issue 4},
year = {2023},
doi = {10.46298/lmcs-19(4:36)2023}
}