Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-3477
Authors: Lauser, Alexander
Title: Formal language theory of logic fragments
Other Titles: Formalsprachliche Theorie der Logikfragmente
Issue Date: 2014
metadata.ubs.publikation.typ: 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
Abstract: 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.
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
diss_druckversion_2014_12_19_veroeffentlichungsversion.pdf1,74 MBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.