Bibliograph. Daten | Abdelaziz, Amir: Separierbarkeit über endlichen Wörtern bei einer Quantorenalternierung. Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Diplomarbeit Nr. 2 (2015). 25 Seiten, deutsch.
|
CR-Klassif. | F.4.3 (Formal Languages) F.4.1 (Mathematical Logic)
|
Kurzfassung | 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.
|
Volltext und andere Links | PDF (434442 Bytes)
|
Abteilung(en) | Universität Stuttgart, Institut für Formale Methoden der Informatik, Formale Konzepte
|
Betreuer | Kufleitner, PD Dr. Manfred |
Eingabedatum | 3. Juli 2018 |
---|