Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen: http://dx.doi.org/10.18419/opus-3477
Autor(en): Lauser, Alexander
Titel: Formal language theory of logic fragments
Sonstige Titel: Formalsprachliche Theorie der Logikfragmente
Erscheinungsdatum: 2014
Dokumentart: Dissertation
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-97834
http://elib.uni-stuttgart.de/handle/11682/3494
http://dx.doi.org/10.18419/opus-3477
Zusammenfassung: The present thesis consists of two parts. Based on syntactic closure axioms of formula sets, the first part gives a formal definition of logic fragments. It also shows the versatileness of this notion of logic fragments, inter alia, giving, C-variety descriptions of logic fragments and abstractly investigating the influence of certain predicates on the expressiveness of logic fragments. The second part considers two-variable first-order logic FO2. A combinatorial description in terms of so-called rankers is given for all full levels as well as all half levels of the quantifier alternation hierarchy of FO2 over the order predicate, both with and without the successor predicate. Also in the second part, effective algebraic criteria describing all full levels as well as all half levels of the quantifier alternation hierarchy of FO2 over several signatures are given, yielding in particular decidability of the definability problem.
Die vorliegende Dissertation besteht aus zwei Teilen. Im ersten Teil wird, basierend auf syntaktischen Abschlusseigenschaften von Formelmengen, eine formale Definition von Logikfragmenten angegeben. Dort wird des Weiteren die Vielseitigkeit dieses Begriffs von Logikfragmenten aufgezeigt, unter anderem durch Beschreibungen von Logikfragmenten durch C-Varietäten und durch Untersuchungen des Einflusses gewisser Prädikate auf die Ausdrucksstärke von Logikfragmenten. Der zweite Teil beschäftigt sich mit dem Zweivariablenfragment FO2 der Logik erster Stufe. Es wird eine kombinatorische Beschreibung durch sogenannte Ranker für alle Volllevel und alle Halblevel der FO2-Quantorenalternierungshierarchie über dem Ordnungsprädikat angegeben, sowohl mit als auch ohne Nachfolgerprädikat. Außerdem werden im zweiten Teil effektive algebraische Kriterien angegeben, die alle Voll- sowie alle Halblevel der FO2-Quantorenalternierungshierarchie über diversen Signaturen beschreiben, woraus sich insbesondere die Entscheidbarkeit des Definierbarkeitsproblems ergibt.
Enthalten in den Sammlungen:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
diss_druckversion_2014_12_19_veroeffentlichungsversion.pdf1,74 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.