Decidable and expressive classes of probabilistic automata (Q1740668)

The contribution discusses the expressive power of certain probabilistic automata. A probabilistic automaton is essentially a (potentially nondeterministic) finite-state automaton whose transitions carry a probability such that the probabilities of all transitions that leave a state by a given symbol sum to \(1\). The probability of a sequence of transitions is simply the product of the individual transition probabilities, and the probability of an input word is the sum of the probabilities of transition sequences for the input word. An input word is accepted by the automaton if its probability exceeds a given threshold (mostly 0.5 in the paper). Probabilistic automata are still very expressive and most problems remain undecidable for them. To this end, the contribution considers \(k\)-hierarchical probabilistic automata, in which the states are partitioned into \(k+1\) classes such that for each state \(q\) in class \(i\), all transitions leaving the state go to states of class \(i\) or higher. In addition, for each input symbol only a single transition for that symbol leaving \(q\) can lead to a state of the same class \(i\). It is demonstrated that \(1\)-hierarchical probabilistic automata can still recognize non-regular languages, but their non-emptiness as well as non-universality problems are decidable and shown to be in EXPTIME as well as PSPACE-hard. Already for \(2\)-hierarchical probabilistic automata, the emptiness problem becomes undecidable, which is also shown in the contribution. Finally, a new sufficient condition is presented that, provided that a \(1\)-hierarchical probabilistic automaton fulfills it, then its accepted language is guaranteed to be regular. The paper is excellently written and contains examples and illustrations. Proof details are provided for all major claims and those proofs are easily understandable and well presented. Overall, anyone with some background knowledge in automata theory as well as a primer in complexity theory can appreciate the contribution fully.