Probabilistic Finite Automaton Emptiness is Undecidable for a Fixed Automaton

Autor:	Rote, Günter
Rok vydání:	2024
Předmět:	Computer Science - Formal Languages and Automata Theory F.1.1 F.4.3
Druh dokumentu:	Working Paper
Popis:	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 decision problem is the starting distribution. For the proof, we use reductions from special instances of the Post Correspondence Problem. We also consider some variations: The input alphabet of the PFA can be restricted to a binary alphabet at the expense of a larger number of states. If we allow a rational output value for each state instead of a yes-no acceptance decision, the number of states can even be reduced to 6. Comment: 28 pages, 2 figures, 3 appendices
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2412.05198 Zobrazit plný text záznamu View this record from Arxiv