Randomization in Automata on Infinite Trees
Randomization in Automata on Infinite Trees
复制标题
无限树自动机中的随机化
DOI：
10.1145/2629336
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
O. Serre
中科院分区：
文献类型：
--
作者：
Arnaud Carayol;Axel Haddad;O. Serre
我们研究在无限二叉树上运行的有限自动机。这样的自动机在输入树上的运行是由自动机的控制状态标记的树：标记是以自顶向下的方式构建的，并且应该与自动机的转换一致。如果通过读取沿分支的状态获得的ω-字满足某些接受条件（通常是ω-正则条件，如b<e:1>或奇偶条件），则运行中的分支是接受的。最后，如果在这棵树上存在一次运行，其中每个分支都接受，则该树被自动机接受。
We study finite automata running over infinite binary trees. A run of such an automaton over an input tree is a tree labeled by control states of the automaton: the labeling is built in a top-down fashion and should be consistent with the transitions of the automaton. A branch in a run is accepting if the ω-word obtained by reading the states along the branch satisfies some acceptance condition (typically an ω-regular condition such as a Büchi or a parity condition). Finally, a tree is accepted by the automaton if there exists a run over this tree in which every branch is accepting.
In this article, we consider two relaxations of this definition, introducing a qualitative aspect. First, we relax the notion of accepting run by allowing a negligible set (in the sense of measure theory) of nonaccepting branches. In this qualitative setting, a tree is accepted by the automaton if there exists a run over this tree in which almost every branch is accepting. This leads to a new class of tree languages, qualitative tree languages. This class enjoys many good properties: closure under union and intersection (but not under complement), and emptiness is decidable in polynomial time. A dual class, positive tree languages, is defined by requiring that an accepting run contains a non-negligeable set of branches.
The second relaxation is to replace the existential quantification (a tree is accepted if there exists some accepting run over the input tree) with a probabilistic quantification (a tree is accepted if almost every run over the input tree is accepting). For the run, we may use either classical acceptance or qualitative acceptance. In particular, for the latter, we exhibit a tight connection with partial observation Markov decision processes. Moreover, if we additionally restrict operation to the Büchi condition, we show that it leads to a class of probabilistic automata on infinite trees enjoying a decidable emptiness problem. To our knowledge, this is the first positive result for a class of probabilistic automaton over infinite trees.