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.
翻译:我们从自动图的模糊程度及其字母大小的角度研究单元和二元性绝对概率性自动数据(PFA)的空洞性和美元-lambda$的可达性问题,并将这些问题的复杂性定性为自动图的模糊程度及其字母的大小,我们的主要结果是,空洞和美元-lambda$的可达性问题在EXPTIME中可以溶解,因为多元的模糊性单一PFA,此外,如果过渡矩阵是二进制的,则我们表明它们是NP。与Exkolem-hard of $-limbda$的可达性和空闲性问题相比,我们表明,即使对于极模糊的单调单调式PFA,这些问题也是不易解决的。对于具有固定和通融通过渡矩阵的二进制多边多式模糊的PFAFA,我们证明$-lambda$的可达性(Dimension 9)、非严格性(discritecion 37)和严格的空性(dition 40)问题,我们证明NPPNP-硬性是硬性。