City Research Online

When are Emptiness and Containment Decidable for Probabilistic Automata?

Daviaud, L. ORCID: 0000-0002-9220-7118, Jurdzinski, M., Lazic, R., Mazowiecki, F., Perez, G. A. and Worrell, J. (2021). When are Emptiness and Containment Decidable for Probabilistic Automata?. Journal of Computer and System Sciences,

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 well known that both problems are undecidable. In this paper 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 (that is known to be undecidable in general) becomes decidable for automata of polynomial ambiguity. We complement this positive result by showing that the emptiness problem remains undecidable even when restricted to automata of linear ambiguity. We then turn to finitely ambiguous automata. Here we give a conditional decidability proof for containment in case one of the automata is assumed to be unambiguous while the other one is allowed to be finitely ambiguous. Part of our proof relies on the decidability of the theory of real exponentiation, which has been shown, subject to Schanuel’s Conjecture, by Macintyre and Wilkie.

Publication Type: Article
Additional Information: © 2021. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Publisher Keywords: Probabilistic automata, Emptiness, Containment, Ambiguity
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Mathematics, Computer Science & Engineering > Computer Science
Date Deposited: 18 Feb 2021 15:39
URI: https://openaccess.city.ac.uk/id/eprint/25690
[img] Text - Accepted Version
This document is not freely accessible due to copyright restrictions.
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Export

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login