Weighted Tree Automata and Quantitative Logics with a Focus on Ambiguity

Authors: 
Paul, Erik
Year: 
2015
Language: 
English
Abstract in English: 
We relate various restrictions of a quantitative logic to subclasses of weighted tree automata. The subclasses are defined by the level of ambiguity allowed in the automata. This yields a generalization of the results by Stephan Kreutzer and Cristian Riveros, who considered the same problem for weighted automata over words. Along the way we also prove that a finitely ambiguous weighted tree automaton can be decomposed into unambiguous ones and define and analyze polynomial ambiguity for tree automata.
AttachmentSize
Diplomarbeit_Erik_Paul.pdf612.23 KB