Probabilistic Finite Automaton Emptiness is undecidable
Probabilistic Finite Automaton Emptiness is undecidable
It is undecidable whether the language recognized by a probabilistic finite automaton is empty. Several other undecidability results, in particular regarding problems about matrix products, are based on this important theorem. We present two proofs of this theorem from the literature in a self-contained way, and we derive some strengthenings. …