Decision Questions for Probabilistic Automata on Small Alphabets

Bell, Paul C.; Semukhin, Pavel

Abstract

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.

Citation

Bell, P. C., & Semukhin, P. (2023). Decision Questions for Probabilistic Automata on Small Alphabets. Logical Methods in Computer Science, 19(4), 1-36. https://doi.org/10.46298/lmcs-19%284%3A36%292023

• Journal Article Type: Article
• Acceptance Date: Nov 9, 2023
• Online Publication Date: Dec 21, 2023
• Publication Date: Dec 21, 2023
• Deposit Date: Feb 8, 2024
• Publicly Available Date: Feb 12, 2024
• Journal: Logical Methods in Computer Science
• Print ISSN: 1860-5974
• Publisher: Logical Methods in Computer Science
• Peer Reviewed: Peer Reviewed
• Volume: 19
• Issue: 4
• Article Number: 36
• Pages: 1-36
• DOI: https://doi.org/10.46298/lmcs-19%284%3A36%292023
• Keywords: General Computer Science; Theoretical Computer Science
• Publisher URL: https://lmcs.episciences.org/