Decision problems for probabilistic and quantum automata
James Worrell ( Oxford University Computing Laboratory )
In this talk we will survey decidability questions in the language theory of probabilistic and quantum finite automata. We will consider language equivalence for probabilistic automata as well as decidability and undecidability results for various versions of the threshold problem for probabilistic and quantum automata. If time permits we will discuss some applications of these results to probabilistic verification.