The Infimum Problem as a Generalization of the Inclusion Problem for Automata

Stefan Borgwardt

AutorIn

Stefan Borgwardt

Titel

The Infimum Problem as a Generalization of the Inclusion Problem for Automata

Zitierfähige Url:

https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-888026

Erstveröffentlichung

2010

Datum der Einreichung

30.09.2010

Datum der Verteidigung

13.10.2010

Abstract (EN)

This thesis is concerned with automata over infinite trees. They are given a labeled infinite tree and accept or reject this tree based on its labels. A generalization of these automata with binary decisions are weighted automata. They do not just decide 'yes' or 'no', but rather compute an arbitrary value from a given algebraic structure, e.g., a semiring or a lattice. When passing from unweighted to weighted formalisms, many problems can be translated accordingly. The purpose of this work is to determine the feasibility of solving the inclusion problem for automata on infinite trees and its generalization to weighted automata, the infimum aggregation problem.

Freie Schlagwörter (DE)

Gewichtete Automaten, Unendliche Bäume, Inklusion

Freie Schlagwörter (EN)

weighted automata, infinite trees, inclusion

Klassifikation (DDC)

004

Klassifikation (RVK)

ST 136

GutachterIn