Probabilistic Regular Expressions and MSO Logic on Finite Trees
Thomas Weidner · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2015
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.