Diploma Thesis DIP-2015-02

BibliographyAbdelaziz, Amir: Separierbarkeit über endlichen Wörtern bei einer Quantorenalternierung.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Diploma Thesis No. 2 (2015).
25 pages, german.
CR-SchemaF.4.3 (Formal Languages)
F.4.1 (Mathematical Logic)
Abstract

Das Separierbarkeitsproblem entspricht der Fragestellung ob für zwei Mengen X und Y ein sogenannter Separator S existiert mit X  S und Y \ S = ;. Man sagt dann, dass S die Menge X von Y trennt. Formale Sprachen können durch prädikatenlogische Formeln definiert werden. Ein bekanntes Logikfragment der prädikatenlogischen Formeln ist 2. Diese Diplomarbeit beschäftigt sich mit der 2-Separierbarkeit von regulären Sprachen, d.h. mit der Entscheidbarkeit ob für zwei reguläre Sprachen L1 und L2 eine dritte Sprache S existiert die durch eine Formel in 2 definiert werden kann und L1 von L2 trennt. Grundlage dafür ist der Artikel Going Higher in the First-Order Quantifier Alternation Hierarchy on Words von Thomas Place und Marc Zeitoun.

Full text and
other links
PDF (434442 Bytes)
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Formal Concepts
Superviser(s)Kufleitner, PD Dr. Manfred
Entry dateJuly 3, 2018
   Publ. Computer Science