Paul C. Bell ; Pavel Semukhin - Decision Questions for Probabilistic Automata on Small Alphabets

lmcs:9753 - Logical Methods in Computer Science, December 21, 2023, Volume 19, Issue 4 - https://doi.org/10.46298/lmcs-19(4:36)2023
Decision Questions for Probabilistic Automata on Small AlphabetsArticle

Authors: Paul C. Bell ; Pavel Semukhin

    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.


    Volume: Volume 19, Issue 4
    Published on: December 21, 2023
    Accepted on: November 9, 2023
    Submitted on: June 30, 2022
    Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Logic in Computer Science

    Consultation statistics

    This page has been seen 521 times.
    This article's PDF has been downloaded 109 times.