
doi: 10.1109/lics.2011.28
We study finite automata running over infinite binary trees and we relax the notion of accepting run by allowing a negligible set (in the sense of measure theory) of non-accepting 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, called the qualitative tree languages that enjoys many properties. Then, we replace the existential quantification -- a tree is accepted if there exists some accepting run over the input tree -- by a probabilistic quantification -- a tree is accepted if almost every run over the input tree is accepting. Together with the qualitative acceptance and the Buchi condition, we obtain a class of probabilistic tree automata with a decidable emptiness problem. To our knowledge, this is the first positive result for a class of probabilistic automaton over infinite trees.
[INFO.INFO-CL] Computer Science [cs]/Computation and Language [cs.CL], Tree Automata, Probabilistic Automata, Markov Decision Process
[INFO.INFO-CL] Computer Science [cs]/Computation and Language [cs.CL], Tree Automata, Probabilistic Automata, Markov Decision Process
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
