Conference item icon

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
Version:
Publisher's Version

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.CONCUR.2017.19

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Oxford college:
Green Templeton College
Role:
Author
Publisher:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik Publisher's website
Volume:
85
Pages:
19:1-19:14
Publication date:
2017-08-01
Acceptance date:
2017-07-07
DOI:
EISSN:
1868-8969
Pubs id:
pubs:738865
URN:
uri:12f0021c-7bae-4f21-a7a2-8e0d06071284
UUID:
uuid:12f0021c-7bae-4f21-a7a2-8e0d06071284
Local pid:
pubs:738865
ISBN:
9783959770484

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP