When are emptiness and containment decidable for probabilistic automata?

Journal of Computer and System Sciences(2021)

引用 3|浏览30
暂无评分
摘要
The emptiness and containment problems for probabilistic automata are natural quantitative generalisations of the classical language emptiness and inclusion problems for Boolean automata. It is known that both problems are undecidable. We provide a more refined view of these problems in terms of the degree of ambiguity of probabilistic automata. We show that a gap version of the emptiness problem (known to be undecidable in general) becomes decidable for automata of polynomial ambiguity. We complement this positive result by showing that emptiness remains undecidable when restricted to automata of linear ambiguity. We then turn to finitely ambiguous automata and give a conditional decidability proof for containment in case one of the automata is assumed to be unambiguous. Part of our proof relies on the decidability of the theory of real exponentiation, proved, subject to Schanuel's Conjecture, by Macintyre and Wilkie.
更多
查看译文
关键词
Probabilistic automata,Emptiness,Containment,Ambiguity
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要