Deciding the Value 1 Problem for Probabilistic Leaktight Automata
Deciding the Value 1 Problem for Probabilistic Leaktight Automata
复制标题
确定概率密封自动机的值 1 问题
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Y. Oualhadj
中科院分区：
文献类型：
--
作者：
Nathanaël Fijalkow;H. Gimbert;Edon Kelmendi;Y. Oualhadj
值1问题是有限词上概率自动机的一个判定问题：给定一个概率自动机，是否有概率任意接近1的词被接受？这个问题最近被证明是无法决定的。我们加强了这一结果，表明即使概率自动机只有一个概率转移，不可判断性仍然成立。我们的主要贡献是引入了一类新的概率自动机，称为无泄漏自动机，对于它，值1问题是可判定的(且是PSPACE-完全的)。我们基于抽象自动机行为的么半群的计算构造了一个算法，并依靠Simon发展的代数技术来证明正确性。这类无泄漏自动机在PSPACE中是可判定的，它包含了值为1的概率自动机(特别是确定性自动机)的所有子类，并且在两个自然合成算子下是封闭的。
The value 1 problem is a decision problem for probabilistic automata over finite words: given a probabilistic automaton, are there words accepted with probability arbitrarily close to 1? This problem was proved undecidable recently. We sharpen this result, showing that the undecidability holds even if the probabilistic automata have only one probabilistic transition. Our main contribution is to introduce a new class of probabilistic automata, called leaktight automata, for which the value 1 problem is shown decidable (and PSPACE-complete). We construct an algorithm based on the computation of a monoid abstracting the behaviors of the automaton, and rely on algebraic techniques developed by Simon for the correctness proof. The class of leaktight automata is decidable in PSPACE, subsumes all subclasses of probabilistic automata whose value 1 problem is known to be decidable (in particular deterministic automata), and is closed under two natural composition operators.