The Library
When are emptiness and containment decidable for probabilistic automata?
Tools
Tools
Tools
Daviaud, Laure, Jurdzinski, Marcin, Lazic, Ranko, Mazowiecki, Filip, Pérez, Guillermo A. and Worrell, James (2021) When are emptiness and containment decidable for probabilistic automata? Journal of Computer and System Sciences, 119 . pp. 78-96. doi:10.1016/j.jcss.2021.01.006
|
PDF
WRAP-When-emptiness-containment-decidable-probalistic-automata-2021.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (1190Kb) | Preview |
Official URL: https://doi.org/10.1016/j.jcss.2021.01.006
Abstract
The emptiness and containment problems for probabilistic automata are natural quantitative generalisations of the classical language emptiness and inclusion problems for Boolean automata. It is known that both problems are undecidable. We provide a more refined view of these problems in terms of the degree of ambiguity of probabilistic automata. We show that a gap version of the emptiness problem (known to be undecidable in general) becomes decidable for automata of polynomial ambiguity. We complement this positive result by showing that emptiness remains undecidable when restricted to automata of linear ambiguity. We then turn to finitely ambiguous automata and give a conditional decidability proof for containment in case one of the automata is assumed to be unambiguous. Part of our proof relies on the decidability of the theory of real exponentiation, proved, subject to Schanuel's Conjecture, by Macintyre and Wilkie.
| Item Type: | Journal Article | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Probabilistic automata , Probabilities | |||||||||||||||||||||
| Journal or Publication Title: | Journal of Computer and System Sciences | |||||||||||||||||||||
| Publisher: | Academic Press | |||||||||||||||||||||
| ISSN: | 0022-0000 | |||||||||||||||||||||
| Official Date: | August 2021 | |||||||||||||||||||||
| Dates: |
|
|||||||||||||||||||||
| Volume: | 119 | |||||||||||||||||||||
| Page Range: | pp. 78-96 | |||||||||||||||||||||
| DOI: | 10.1016/j.jcss.2021.01.006 | |||||||||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||||||||
| Publication Status: | Published | |||||||||||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||||||||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
