Series, Weighted Automata, Probabilistic Automata and Probability Distributions for Unranked Trees.

Abstract : We study tree series and weighted tree automata over unranked trees. The message is that recognizable tree series for unranked trees can be defined and studied from recognizable tree series for binary representations of unranked trees. For this we prove results of Denis et al (2007) as follows. We extend hedge automata -- a class of tree automata for unranked trees -- to weighted hedge automata. We define weighted stepwise automata as weighted tree automata for binary representations of unranked trees. We show that recognizable tree series can be equivalently defined by weighted hedge automata or weighted stepwise automata. Then we consider real-valued tree series and weighted tree automata over the field of real numbers. We show that the result also holds for probabilistic automata -- weighted automata with normalisation conditions for rules. We also define convergent tree series and show that convergence properties for recognizable tree series are preserved via binary encoding. From Etessami and Yannakakis (2009), we present decidability results on probabilistic tree automata and algorithms for computing sums of convergent series. Last we show that streaming algorithms for unranked trees can be seen as slight transformations of algorithms on the binary representations.
Type de document :
Rapport
[Research Report] RR-7200, INRIA. 2010, pp.23
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00455955
Contributeur : Marc Tommasi <>
Soumis le : mardi 9 mars 2010 - 08:12:54
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mercredi 30 novembre 2016 - 15:15:03

Fichier

RR-7200.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00455955, version 2

Collections

Citation

Édouard Gilbert, Rémi Gilleron, Marc Tommasi. Series, Weighted Automata, Probabilistic Automata and Probability Distributions for Unranked Trees.. [Research Report] RR-7200, INRIA. 2010, pp.23. 〈inria-00455955v2〉

Partager

Métriques

Consultations de la notice

588

Téléchargements de fichiers

234