Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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 ISSN 0022-0000.

[img]
Preview
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

Request Changes to record.

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:
DateEvent
August 2021Published
10 February 2021Available
5 February 2021Accepted
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
Date of first compliant deposit: 10 February 2021
Date of first compliant Open Access: 10 February 2022
RIOXX Funder/Project Grant:
Project/Grant IDRIOXX Funder NameFunder ID
EP/P020992/1 [EPSRC] Engineering and Physical Sciences Research Councilhttp://dx.doi.org/10.13039/501100000266
EP/N008197/1[EPSRC] Engineering and Physical Sciences Research Councilhttp://dx.doi.org/10.13039/501100000266
RF-2017-579Leverhulme Trusthttp://dx.doi.org/10.13039/501100000275
ANR-10-IDEX-03-02[ANR] Agence Nationale de la Recherchehttp://dx.doi.org/10.13039/501100001665
UNSPECIFIEDFonds De La Recherche Scientifique - FNRShttp://dx.doi.org/10.13039/501100002661
EP/T018313/1[EPSRC] Engineering and Physical Sciences Research Councilhttp://dx.doi.org/10.13039/501100000266
Related URLs:
  • Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us