首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:When is Containment Decidable for Probabilistic Automata?
  • 作者:Laure Daviaud ; Marcin Jurdzinski ; Ranko Lazic
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:107
  • 页码:121:1-121:14
  • DOI:10.4230/LIPIcs.ICALP.2018.121
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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.
  • 关键词:Probabilistic automata; Containment; Emptiness; Ambiguity
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有