City Research Online

When is Containment Decidable for Probabilistic Automata?

Daviaud, L., Jurdziński, M., Lazić, R., Mazowiecki, F., Pérez, G. A. and Worrell, J. (2018). When is Containment Decidable for Probabilistic Automata? In: 45th International Colloquium on Automata, Languages, and Programming. Leibniz International Proceedings in Informatics (LIPIcs), 107. (121:1-121:4). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-076-7

Abstract

The containment problem for quantitative automata is the natural quantitative generalisation of the classical language inclusion problem for Boolean automata. We study it for probabilistic automata, where it is known to be undecidable in general. We restrict our study to the class of probabilistic automata with bounded ambiguity. There, we show decidability (subject to Schanuel's conjecture) when one of the automata is assumed to be unambiguous while the other one is allowed to be finitely ambiguous. Furthermore, we show that this is close to the most general decidable fragment of this problem by proving that it is already undecidable if one of the automata is allowed to be linearly ambiguous.

Publication Type: Conference or Workshop Item (Paper)
Additional Information: © Laure Daviaud, Marcin Jurdziński, Ranko Lazić, Filip Mazowiecki, Guillermo A. Pérez, and James Worrell; licensed under Creative Commons License CC-BY
Publisher Keywords: Probabilistic automata, Containment, Emptiness, Ambiguity
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Mathematics, Computer Science & Engineering > Computer Science
URI: http://openaccess.city.ac.uk/id/eprint/21290
[img]
Preview
Text - Accepted Version
Available under License Creative Commons: Attribution 3.0.

Download (636kB) | Preview

Export

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login