TY - GEN
T1 - When is containment decidable for probabilistic automata?
AU - Daviaud, Laure
AU - Jurdziński, Marcin
AU - Lazić, Ranko
AU - Mazowiecki, Filip
AU - Pérez, Guillermo A.
AU - Worrell, James
N1 - Funding Information:
by the EPSRC grant
Funding Information:
1 R. Lazić has been supported by a Leverhulme Trust Research Fellowship RF-2017-579. 2 F. Mazowiecki has been supported by the French National Research Agency (ANR) in the frame of the “Investments for the future” Programme IdEx Bordeaux (ANR-10-IDEX-03-02). 3 G. A. Pérez has been supported by an F.R.S.-FNRS Aspirant fellowship and an FWA postdoc fellowship. 4 J. Worrell has been supported by the EPSRC Fellowship EP/N008197/1.
Funding Information:
R. Lazić has been supported by a Leverhulme Trust Research Fellowship RF-2017-579. 2 F. Mazowiecki has been supported by the French National Research Agency (ANR) in the frame of the
Funding Information:
“ Investments for the future” Programme IdEx Bordeaux (ANR-10-IDEX-03-02). 3 G. A. Pérez has been supported by an F.R.S.-FNRS Aspirant fellowship and an FWA postdoc fellowship. 4 J. Worrell has been supported by the EPSRC Fellowship EP/N008197/1.
Publisher Copyright:
© 2018 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
PY - 2018/7/1
Y1 - 2018/7/1
N2 - 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.
AB - 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.
KW - Ambiguity
KW - Containment
KW - Emptiness
KW - Probabilistic automata
UR - http://www.scopus.com/inward/record.url?scp=85049796902&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2018.121
DO - 10.4230/LIPIcs.ICALP.2018.121
M3 - Conference contribution
AN - SCOPUS:85049796902
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
A2 - Kaklamanis, Christos
A2 - Marx, Daniel
A2 - Chatzigiannakis, Ioannis
A2 - Sannella, Donald
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
Y2 - 9 July 2018 through 13 July 2018
ER -