Showing cs.FLShow all
2 papers · 1 filter
cs.FL2024
Probabilistic Finite Automaton Emptiness is Undecidable for a Fixed Automaton
Günter Rote
We construct a probabilistic finite automaton (PFA) with 7 states and an input alphabet of 5 symbols for which the PFA Emptiness Problem is undecidable. The only input for the deci…
cs.FL2024
Probabilistic Finite Automaton Emptiness is undecidable
Günter Rote
It is undecidable whether the language recognized by a probabilistic finite automaton is empty. Several other undecidability results, in particular regarding problems about matrix…