inria-00455955, version 1

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

Édouard Gilbert () ^1, 2, Rémi Gilleron () ^1, 2, 3, Marc Tommasi () ^1, 2, 3

N° RR-7200 (2010)

• 1 :  Laboratoire d'Informatique Fondamentale de Lille (LIFL)
• http://www.lifl.fr/
  CNRS : UMR8022 – Université Lille I - Sciences et technologies – Université Lille III - Sciences humaines et sociales – INRIA Bâtiment M3 59655 Villeneuve d'Ascq Cédex France
• 2 :  MOSTRARE (INRIA Lille - Nord Europe)
• 
  INRIA – CNRS : UMR8022 – Université Lille I - Sciences et technologies – Université Lille III - Sciences humaines et sociales France
• 3 :  GRAPPA (LIFL)
• http://www.grappa.univ-lille3.fr
  CNRS : UMR8022 – Université Lille III - Sciences humaines et sociales – Université Lille I - Sciences et technologies Maison de la recherche, domaine Universitaire Pont de Bois Université Charles de Gaulle - Lille 3 59653 Villeneuve d'Ascq CEDEX France

Versions disponibles :  v1 (11-02-2010) v2 (09-03-2010)

Références bibliographiques

• Type de publication : Rapports
• Domaine : Informatique/Apprentissage
• Titre : Series, Weighted Automata, Probabilistic Automata and Probability Distributions for Unranked Trees.
• Résumé : 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.
• Langue du document : Anglais
• Type de rapport : Rapport de recherche
• Nombre de pages : 23
• Date de publication : 11/02/2010
• Mots-clés : Tree automata – weighted automata – xml
• Date de rédaction : 11/02/2010
• Référence interne : RR-7200
• Projet ANR :

  Référence du projet

  LAMPADA ANR-09-EMER-007

Liste des fichiers attachés à ce document :

• inria-00455955, version 1
• http://hal.inria.fr/inria-00455955
• oai:hal.inria.fr:inria-00455955
• Contributeur : Marc Tommasi <>
• Soumis le : Jeudi 11 Février 2010, 13:44:40
• Dernière modification le : Jeudi 11 Février 2010, 14:39:37