City Research Online

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 Science & Technology > Computer Science
SWORD Depositor:	Symplectic Administrator

Export

Downloads