2026-07-31T19:13:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9125 2024-03-06T10:43:25Z ddc:004 open_access

When is Containment Decidable for Probabilistic Automata? Daviaud, Laure Jurdzinski, Marcin Lazic, Ranko Mazowiecki, Filip Pérez, Guillermo A. Worrell, James Probabilistic automata Containment Emptiness Ambiguity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Laure Daviaud and Marcin Jurdzinski and Ranko Lazic and Filip Mazowiecki and Guillermo A. Pérez and James Worrell 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.121 urn:nbn:de:0030-drops-91251 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.121 eng https://creativecommons.org/licenses/by/3.0/legalcode