Decision Questions for Probabilistic Automata on Small Alphabets
(2023)
Journal Article
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
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... Read More about Decision Questions for Probabilistic Automata on Small Alphabets.