Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen: http://dx.doi.org/10.18419/opus-9782
Autor(en): Abdelaziz, Amir
Titel: Separierbarkeit über endlichen Wörtern bei einer Quantorenalternierung
Sonstige Titel: Separation over finite words for one quantifier alternation
Erscheinungsdatum: 2015
Dokumentart: Abschlussarbeit (Diplom)
Seiten: 24
URI: http://elib.uni-stuttgart.de/handle/11682/9799
http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-97998
http://dx.doi.org/10.18419/opus-9782
Zusammenfassung: 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.
Enthalten in den Sammlungen:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
Ausarbeitung.pdf410,62 kBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.