Jelenlegi hely
Tanszékcsoporti szeminárium
Félév:
2015/16 I. félév
Helyszín:
Árpád tér 2. II. em. 220. sz.
Dátum:
2015-09-22
Időpont:
14:00-15:00
Előadó:
Doreen Heusel & Thomas Weidner (Universitat Leipzig)
Cím:
Weighted Tree Automata and Regular Expressions
Absztrakt:
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.