Probabilistic automata of bounded ambiguity
Probabilistic automata are a computational model introduced by Michael Rabin, extending nondeterministic finite automata with probabilistic transitions. Despite its simplicity, this model is very expressive and many of the associated algorithmic questions are undecidable. In this work we focus on th...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Published: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2017
|
| _version_ | 1797054580438073344 |
|---|---|
| author | Fijalkow, N Riveros, C Worrell, J |
| author_facet | Fijalkow, N Riveros, C Worrell, J |
| author_sort | Fijalkow, N |
| collection | OXFORD |
| description | Probabilistic automata are a computational model introduced by Michael Rabin, extending nondeterministic finite automata with probabilistic transitions. Despite its simplicity, this model is very expressive and many of the associated algorithmic questions are undecidable. In this work we focus on the emptiness problem, which asks whether a given probabilistic automaton accepts some word with probability higher than a given threshold. We consider a natural and well-studied structural restriction on automata, namely the degree of ambiguity, which is defined as the maximum number of accepting runs over all words. We observe that undecidability of the emptiness problem requires infinite ambiguity and so we focus on the case of finitely ambiguous probabilistic automata. Our main results are to construct efficient algorithms for analysing finitely ambiguous probabilistic automata through a reduction to a multi-objective optimisation problem, called the stochastic path problem. We obtain a polynomial time algorithm for approximating the value of finitely ambiguous probabilistic automata and a quasi-polynomial time algorithm for the emptiness problem for 2-ambiguous probabilistic automata. |
| first_indexed | 2024-03-06T18:59:13Z |
| format | Conference item |
| id | oxford-uuid:12f0021c-7bae-4f21-a7a2-8e0d06071284 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T18:59:13Z |
| publishDate | 2017 |
| publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| record_format | dspace |
| spelling | oxford-uuid:12f0021c-7bae-4f21-a7a2-8e0d060712842022-03-26T10:10:53ZProbabilistic automata of bounded ambiguityConference itemhttp://purl.org/coar/resource_type/c_5794uuid:12f0021c-7bae-4f21-a7a2-8e0d06071284Symplectic Elements at OxfordSchloss Dagstuhl - Leibniz-Zentrum für Informatik2017Fijalkow, NRiveros, CWorrell, JProbabilistic automata are a computational model introduced by Michael Rabin, extending nondeterministic finite automata with probabilistic transitions. Despite its simplicity, this model is very expressive and many of the associated algorithmic questions are undecidable. In this work we focus on the emptiness problem, which asks whether a given probabilistic automaton accepts some word with probability higher than a given threshold. We consider a natural and well-studied structural restriction on automata, namely the degree of ambiguity, which is defined as the maximum number of accepting runs over all words. We observe that undecidability of the emptiness problem requires infinite ambiguity and so we focus on the case of finitely ambiguous probabilistic automata. Our main results are to construct efficient algorithms for analysing finitely ambiguous probabilistic automata through a reduction to a multi-objective optimisation problem, called the stochastic path problem. We obtain a polynomial time algorithm for approximating the value of finitely ambiguous probabilistic automata and a quasi-polynomial time algorithm for the emptiness problem for 2-ambiguous probabilistic automata. |
| spellingShingle | Fijalkow, N Riveros, C Worrell, J Probabilistic automata of bounded ambiguity |
| title | Probabilistic automata of bounded ambiguity |
| title_full | Probabilistic automata of bounded ambiguity |
| title_fullStr | Probabilistic automata of bounded ambiguity |
| title_full_unstemmed | Probabilistic automata of bounded ambiguity |
| title_short | Probabilistic automata of bounded ambiguity |
| title_sort | probabilistic automata of bounded ambiguity |
| work_keys_str_mv | AT fijalkown probabilisticautomataofboundedambiguity AT riverosc probabilisticautomataofboundedambiguity AT worrellj probabilisticautomataofboundedambiguity |