Randomisation in Automata on Infinite Trees

Abstract : 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 labelling 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 paper, 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 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, qualitative tree languages. This class enjoys many good properties: closure under union and intersection (but not under complement), 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) by 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 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.
Type de document :
Article dans une revue
ACM Transactions on Computational Logic, Association for Computing Machinery, 2014, 15 (3), pp.24. 〈10.1145/2629336〉
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01260669
Contributeur : Olivier Serre <>
Soumis le : vendredi 22 janvier 2016 - 14:45:11
Dernière modification le : jeudi 5 juillet 2018 - 14:46:13
Document(s) archivé(s) le : vendredi 11 novembre 2016 - 16:12:00

Fichier

CHS13_ACM_ToCL.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Arnaud Carayol, Axel Haddad, Olivier Serre. Randomisation in Automata on Infinite Trees. ACM Transactions on Computational Logic, Association for Computing Machinery, 2014, 15 (3), pp.24. 〈10.1145/2629336〉. 〈hal-01260669〉

Partager

Métriques

Consultations de la notice

177

Téléchargements de fichiers

61