Student Thesis STUD-2297

BibliographyKausch, Jonathan: Einfache Logikfragmente mit Nachfolgerrelation über unendlichen Wörtern.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Student Thesis No. 2297 (2011).
42 pages, german.
CR-SchemaF.4.1 (Mathematical Logic)
F.4.3 (Formal Languages)
Abstract

Titel: Einfache Logikfragmente mit Nachfolgerrelation über unendlichen Wörtern Author: Jonathan Kausch

Die sternfreien Sprachen stellen eine wichtige Unterklasse der regulären Sprachen dar. Sie sind reguläre Ausdrücke, die ohne Stern, aber mit Komplementbildung definiert werden können. Über die Anzahl der Konkatenationen erhält man die Tiefe der sogenannten Dot-Depth Hierarchie. Die erste Stufe der Dot-Depth Hierarchie entspricht booleschen Kombinationen von prädikatenlogischen Formeln (FO) in Pränexnormalform ohne Quantorenalternierung (d.h. mit nur einem Block von Quantoren) mit [<,+1,min,max]. Eine algebraische Eigenschaft für die Stufe 1 der Dot-Depth Hierarchie wurde von Knast für endliche Wörter gefunden. Mit zusätzlichen topologischen Eigenschaften lassen sich die Resultate auf unendliche Wörter übertragen.

In dieser Arbeit wird die, von Knast gefundene, Eigenschaft erstmalig auf unendliche Wörter übertragen. Wie sich herausstellt, liefert diese Eigenschaft selbiges Logikfragment von Formeln ohne Quantorenalternierung mit [<,+1,min]. Außerdem wird ein vereinfachter Beweis des sogenannten Wreath-Product-Principles vorgestellt, welches eine direkte Beziehung von Formeln mit [<,+1,min,max] zu Formeln mit nur [<] herstellt.

Full text and
other links
PDF (414107 Bytes)
Access to students' publications restricted to the faculty due to current privacy regulations
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Superviser(s)Kufleitner, Manfred
Entry dateFebruary 15, 2011
   Publ. Computer Science