Tools
Tools
Bell, PC and Semukhin, P (2023) Decision questions for probabilistic automata on small alphabets. Logical Methods in Computer Science, 19 (4). 36:1-36:22. ISSN 1860-5974
|
Text
DECISION QUESTIONS FOR PROBABILISTIC AUTOMATA ON SMALL ALPHABETS.pdf - Published Version Available under License Creative Commons Attribution. Download (468kB) | Preview |
Abstract
We study the emptiness and λ-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 λ-reachability are solvable in EXPTIME for polynomially ambiguous unary PFA and if, in addition, the transition matrix is over {0, 1}, we show they are in NP. In contrast to the Skolem-hardness of the λ-reachability and emptiness problems for exponentially ambiguous unary PFA, we show that these problems are NP-hard even for finitely ambiguous unary PFA. We also show that the value of a polynomially ambiguous PFA can be computed in EXPTIME. For binary polynomially ambiguous PFA with commuting transition matrices, we prove NP-hardness of the λ-reachability (dimension 9), nonstrict emptiness (dimension 37) and strict emptiness (dimension 40) problems.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | 0101 Pure Mathematics; 0802 Computation Theory and Mathematics; 0803 Computer Software |
| Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
| Divisions: | Computer Science & Mathematics |
| Publisher: | Episciences |
| SWORD Depositor: | A Symplectic |
| Date Deposited: | 15 Aug 2024 10:09 |
| Last Modified: | 15 Aug 2024 10:15 |
| DOI or ID number: | 10.46298/lmcs-19(4:36)2023 |
| URI: | https://researchonline.ljmu.ac.uk/id/eprint/23959 |
 |
View Item |