Weighted Automata and Weighted Logics over Tree-like Structures.
Christian Mathissen · 2009
In theoretical computer science the connection between automata and logic is of fundamental importance. This connection was first considered by Büchi and Elgot in the 1960s, when they showed that the languages accepted by finite automata are precisely those languages that can be defined in monadic second-order logic (MSO). In this thesis we consider extensions of Büchi’s and Elgot’s theorem into two directions. First, we consider classes of objects which are more general than words and carry a tree-like structure. Second, we consider quantitative aspects and investigate weighted automata operating on these structures. The study of weighted automata goes back to the work of Schützenberger. He equipped the transitions of an automaton additionally with a weight and studied the behavior of such a device which is now a formal power series, i.e. a mapping assigning to a word an element of a semiring. A semiring is the algebraic structure that carries the weights. For example, the natural numbers form a semiring, but also the probabilistic semiring given by the interval [0,1] together with the max-operator and the usual multiplication is a semiring. This thesis investigates different weighted automaton models over tree-like structures such as texts, nested words and hedges, which have already been considered in the literature. We