Conference item
Probabilistic automata of bounded ambiguity
- Abstract:
-
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 restricti...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Version of record, pdf, 579.7KB)
-
- Publisher copy:
- 10.4230/LIPIcs.CONCUR.2017.19
Authors
Bibliographic Details
- Publisher:
- Schloss Dagstuhl - Leibniz-Zentrum für Informatik Publisher's website
- Host title:
- LIPIcs
- Journal:
- LIPIcs Journal website
- Volume:
- 85
- Pages:
- 19:1-19:14
- Publication date:
- 2017-08-01
- Acceptance date:
- 2017-07-07
- DOI:
- EISSN:
-
1868-8969
- ISBN:
- 9783959770484
Item Description
- Pubs id:
-
pubs:738865
- UUID:
-
uuid:12f0021c-7bae-4f21-a7a2-8e0d06071284
- Local pid:
- pubs:738865
- Source identifiers:
-
738865
- Deposit date:
- 2019-06-12
Terms of use
- Copyright holder:
- Fijalkow et al
- Copyright date:
- 2017
- Notes:
- © Nathanaël Fijalkow, Cristian Riveros, and James Worrell; licensed under Creative Commons License CC-BY
- Licence:
- CC Attribution (CC BY)
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record