Probabilistic Finite Automaton Emptiness is Undecidable for a Fixed Automaton
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929618478432256 |
|---|---|
| author | Rote, Günter |
| author_facet | Rote, Günter |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_05198 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Probabilistic Finite Automaton Emptiness is Undecidable for a Fixed Automaton Rote, Günter Formal Languages and Automata Theory F.1.1; F.4.3 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. |
| title | Probabilistic Finite Automaton Emptiness is Undecidable for a Fixed Automaton |
| topic | Formal Languages and Automata Theory F.1.1; F.4.3 |
| url | https://arxiv.org/abs/2412.05198 |