论文标题
概率有限自动机的切割点隔离的可决定性在结合的输入
Decidability of cutpoint isolation for probabilistic finite automata on letter-bounded inputs
论文作者
论文摘要
我们表明了令人惊讶的结果，即概率有限自动机（PFA）可确定切割点隔离问题，其中输入单词是从包含字母的无上下文语言中获取的。当$ \ mathcal {l} \ subseteq a_1^*a_2^*a_2^*\ cdots a_ \ ell^*$ for某些有限$ \ ell> 0时，每一个字母在每个字母之间是独特的，一种$ \ mathcal {l} \ subseteq a_1^*a_1^*$ a_1^*a_2^*$当$ \ subseteq a_1^*$当$ \ subseteq a_1^*$当$ \ subseteq a_1^*$时，每一个字母在每个字母都是独特的地方时。当无法随意接近时，就会隔离它。这个问题的可决定性与PFA的（严格）空虚问题的情况形成了鲜明的对比，PFA的（严格的）空虚问题在PFA的更严重限制下是不可证明的，具有多项式的歧义，委托矩阵和对字母所包含的语言的交换性矩阵和投入的投入，以及PFA对PFA的注射性问题，以及PFA不可否认的语言。我们提供了一种建设性的非确定算法来解决切割点的隔离问题，即使PFA呈指数性模棱两可，该算法也存在。我们还表明，这个问题至少是NP-HARD，并使用我们的决策程序解决了几个相关问题。
We show the surprising result that the cutpoint isolation problem is decidable for Probabilistic Finite Automata (PFA) where input words are taken from a letter-bounded context-free language. A context-free language $\mathcal{L}$ is letter-bounded when $\mathcal{L} \subseteq a_1^*a_2^* \cdots a_\ell^*$ for some finite $\ell > 0$ where each letter is distinct. A cutpoint is isolated when it cannot be approached arbitrarily closely. The decidability of this problem is in marked contrast to the situation for the (strict) emptiness problem for PFA which is undecidable under the even more severe restrictions of PFA with polynomial ambiguity, commutative matrices and input over a letter-bounded language as well as to the injectivity problem which is undecidable for PFA over letter-bounded languages. We provide a constructive nondeterministic algorithm to solve the cutpoint isolation problem, which holds even when the PFA is exponentially ambiguous. We also show that the problem is at least NP-hard and use our decision procedure to solve several related problems.
