Publication
Title
When is containment decidable for probabilistic automata?
Author
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 Schanuels 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.
Language
English
Source (journal)
LIPIcs : Leibniz International Proceedings in Informatics. - Place of publication unknown
Source (book)
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) / Chatzigiannakis, Ioannis [edit.]; et al.
Publication
Germany : Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik , 2018
ISBN
978-3-95977-076-7
Volume/pages
107 (2018) , 14 p.
Article Reference
12
Medium
E-only publicatie
Full text (Publisher's DOI)
Full text (open access)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
External links
Record
Identification
Creation 19.11.2018
Last edited 12.10.2020