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.
Document type :
Reports
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/inria-00455955
Contributor : Marc Tommasi <>
Submitted on : Tuesday, March 9, 2010 - 8:12:54 AM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on : Wednesday, November 30, 2016 - 3:15:03 PM

File

RR-7200.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

629

Files downloads

310