License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.121
URN: urn:nbn:de:0030-drops-91251
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9125/
Go to the corresponding LIPIcs Volume Portal

Daviaud, Laure ; Jurdzinski, Marcin ; Lazic, Ranko ; Mazowiecki, Filip ; Pérez, Guillermo A. ; Worrell, James

When is Containment Decidable for Probabilistic Automata?

pdf-format:
LIPIcs-ICALP-2018-121.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{daviaud_et_al:LIPIcs:2018:9125,
  author =	{Laure Daviaud and Marcin Jurdzinski and Ranko Lazic and Filip Mazowiecki and Guillermo A. P{\'e}rez and James Worrell},
  title =	{{When is Containment Decidable for Probabilistic Automatal}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{121:1--121:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9125},
  URN =		{urn:nbn:de:0030-drops-91251},
  doi =		{10.4230/LIPIcs.ICALP.2018.121},
  annote =	{Keywords: Probabilistic automata, Containment, Emptiness, Ambiguity}
}

Keywords: Probabilistic automata, Containment, Emptiness, Ambiguity
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI