Probabilistic Finite Automaton Emptiness is undecidable
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929375893520384 |
|---|---|
| author | Rote, Günter |
| author_facet | Rote, Günter |
| contents | 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 three proofs of this theorem from the literature in a self-contained way, and we derive some strengthenings. For example, we show that the problem remains undecidable for a fixed probabilistic finite automaton with 11 states, where only the starting distribution is given as input. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_03035 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Probabilistic Finite Automaton Emptiness is undecidable Rote, Günter Formal Languages and Automata Theory F.1.1; F.4.3 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 three proofs of this theorem from the literature in a self-contained way, and we derive some strengthenings. For example, we show that the problem remains undecidable for a fixed probabilistic finite automaton with 11 states, where only the starting distribution is given as input. |
| title | Probabilistic Finite Automaton Emptiness is undecidable |
| topic | Formal Languages and Automata Theory F.1.1; F.4.3 |
| url | https://arxiv.org/abs/2405.03035 |