Vergleich von Erkennbarkeit sowie Definierbarkeit gewichteter Baumsprachen über Multioperator- und Baumvaluierungsmonoiden

Date

Apr 26, 2013

Time

1:00 PM - 2:00 PM

Speaker

Markus Teichmann

Language

de

Main Topic

Informatik

Other Topics

Informatik

Description

In der theoretischen Informatik spielen formale Sprachen eine wesentliche Rolle, beispielweise beim Model Checking, formaler Semantik oder in der Verarbeitung von natürlicher Sprache. Besondere Relevanz kommt dabei quantitativen Eigenschaften von formalen Baumsprachen zu. Endliche gewichtete Automaten und gewichtete Logiken werden eingesetzt um die oft unendlichen Sprachen endlich zu repräsentieren. Dabei liegt ein besonderer Fokus auf einer möglichst allgemeinen Definition der Mechanismen. In dieser Diplomarbeit werden zwei spezielle algebraische Strukturen als Basis für gewichtete Automaten und Logiken betrachtet. Multioperatormonoide erlauben sehr flexible lokale Gewichtsberechnung, wohingegen Baumvaluierungsmonoide lokale Gewichte global akkumulieren. Es wird gezeigt, dass die zu den Monoiden gehörenden gewichteten Baumautomaten wechselseitig durch einen Automaten über dem jeweilig anderen Monoidtyp simuliert werden können ohne die erkannte Sprache zu ändern. Die mit den Monoiden assoziierten gewichteten Logiken, die mit den entsprechenden Automaten durch ein Büchi/Elgot-Resultat verbunden sind, können durch syntaktische und semantikerhaltende Transformationen in eine Formel der entsprechend anderen Logik überführt werden.

Last modified: Apr 26, 2013, 9:51:34 AM