When are emptiness and containment decidable for probabilistic automata?

Daviaud, Laure, Jurdziński, Marcin, Lazić, 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. ISSN 0022-0000

Full text not available from this repository. (Request a copy)

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:	Article
Additional Information:	Funding Information: This work was supported by the EPSRC grant EP/P020992/1 and the EPSRC fellowship EP/N008197/1. R. Lazić was also supported by a Leverhulme Trust Research Fellowship RF-2017-579; F. Mazowiecki, by the French National Research Agency (ANR) in the frame of the “Investments for the future” Programme IdEx Bordeaux (ANR-10-IDEX-03-02); G. A. Pérez, by an F.R.S.-FNRS Aspirant fellowship and an FWA postdoc fellowship. L. Daviaud was affiliated to the University of Warwick when this work started and is now supported by the EPSRC grant EP/T018313/1.
Uncontrolled Keywords:	ambiguity,containment,emptiness,probabilistic automata,theoretical computer science,computer networks and communications,computational theory and mathematics,applied mathematics ,/dk/atira/pure/subjectarea/asjc/2600/2614
Faculty \ School:	Faculty of Science > School of Computing Sciences
Related URLs:	http://www.scopus.com/inward/record.url?... https://openaccess.city.ac.uk/id/eprint/...
Depositing User:	LivePure Connector
Date Deposited:	07 Jun 2023 13:30
Last Modified:	07 Jun 2023 13:30
URI:	https://ueaeprints.uea.ac.uk/id/eprint/92312
DOI:	10.1016/j.jcss.2021.01.006

Actions (login required)

View Item