When are emptiness and containment decidable for probabilistic automata?
When are emptiness and containment decidable for probabilistic automata?
复制标题
概率自动机什么时候可以判定空性和包含性？
DOI：
10.1016/j.jcss.2021.01.006
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Daviaud L
中科院分区：
文献类型：
--
作者：
Daviaud L
概率自动机的空性和包含性问题是经典布尔自动机空性和包含性问题的自然定量推广。众所周知，这两个问题都是不可判定的。我们提供了一个更精细的查看这些问题的概率自动机的模糊程度。我们表明，空性问题的间隙版本（已知是不可判定的一般）成为多项式模糊自动机的判定。我们补充这一积极的结果表明，空性仍然是不可判定的线性模糊自动机时，限制。然后，我们转向二义性自动机，并给出一个有条件的可判定性证明的情况下，自动机之一，被假定为是明确的。我们的部分证明依赖于真实的指数化理论的可判定性，麦金太尔和威尔基根据沙努尔猜想证明了这一点。
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.
确定概率密封自动机的值 1 问题
DOI：
--
发表时间：
2011
期刊：
2012 27th Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
Nathanaël Fijalkow;H. Gimbert;Edon Kelmendi;Y. Oualhadj
通讯作者：
Y. Oualhadj
确定多项式模糊最小加自动机的无歧义性和顺序性
DOI：
--
发表时间：
2009
期刊：
Symposium on Theoretical Aspects of Computer Science
影响因子：
--
作者：
D. Kirsten;S. Lombardy
通讯作者：
S. Lombardy
马尔可夫链的可达性问题
影响因子：
0.5
作者：
Akshay S
通讯作者：
Akshay S