Weighted tree automata and quantitative logics with a focus on ambiguity

Description

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.

Links & Downloads

1. urn:nbn:de:bsz:15-qucosa2-164548
2. https://ul.qucosa.de/id/qucosa%3A16454
3. https://ul.qucosa.de/api/qucosa%3A16454/attachment/ATT-0/

Tags

info:eu-repo/classification/ddc/000

ddc:000

Additional Fields

Identifer	oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:16454
Date	20 October 2017
Creators	Paul, Erik
Contributors	Droste, Manfred, Universität Leipzig
Source Sets	Hochschulschriftenserver (HSSS) der SLUB Dresden
Language	English
Detected Language	English
Type	info:eu-repo/semantics/acceptedVersion, doc-type:masterThesis, info:eu-repo/semantics/masterThesis, doc-type:Text
Rights	info:eu-repo/semantics/openAccess
Relation	urn:nbn:de:bsz:15-qucosa2-163403, qucosa:16340