Jelenlegi hely

Tanszékcsoporti szeminárium

2015/16 I. félév
Árpád tér 2. II. em. 220. sz.
Doreen Heusel & Thomas Weidner (Universitat Leipzig)
Weighted Tree Automata and Regular Expressions
Doreen  Heusel
(Universitat Leipzig)

Weighted Tree Automata and Regular Expressions over Valuation Monoids

Trees or terms are one of the most fundamental concepts both in
mathematics and in computer science. Thus, weighted tree automata gained a
lot attention during the last decades.  Usually, the weight of a run is
computed locally
by a binary operation. Chatterjee, Doyen, and Henzinger presented a new
approach for strings with real numbers as weights. The weight of a run is
now determined by a global valuation function. An example of such a
valuation function is the average of the weights. For strings, this idea
was generalized by Droste and Meinecke to more general weight structures,
called valuation monoids. Recently Droste, Gotze, Marker, and Meinecke
adapted this concept to weighted tree automata.

Here, we define rational expressions for trees over tree valuation monoids
and show that rational tree series and formal tree series which are
accepted by weighted tree automata are expressively equivalent over Cauchy
unital tree valuation monoid. Cauchy unital tree valuation monoid allow us
to decompose the Valuation function into a family of operations. We use
these restrictions to simulate concatenations of tree series by direct
automata-theoretic constructions. Thus we can give a constructive proof of
the equivalence result.

* * *

Thomas Weidner
(Universitat Leipzig)

Probabilistic Regular Expressions and MSO Logic on Finite Trees

We introduce probabilistic regular tree expressions and give a Kleene-like
theorem for probabilistic tree automata (PTA). Furthermore, we define
probabilistic MSO logic. This logic is more expressive than PTA. We define
bottom-up PTA, which are strictly more expressive than PTA. Using
bottom-up PTA, we prove a Büchi-like theorem for probabilistic MSO logic.
We obtain a Nivat-style theorem as an additional result.