Formal language theory of logic fragments

Lauser, Alexander

Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen: http://dx.doi.org/10.18419/opus-3477

Langanzeige der Metadaten

DC Element	Wert	Sprache
dc.contributor.advisor	Diekert, Volker (Prof. Dr.)	de
dc.contributor.author	Lauser, Alexander	de
dc.date.accessioned	2015-01-28	de
dc.date.accessioned	2016-03-31T08:02:02Z	-
dc.date.available	2015-01-28	de
dc.date.available	2016-03-31T08:02:02Z	-
dc.date.issued	2014	de
dc.identifier.other	425465454	de
dc.identifier.uri	http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-97834	de
dc.identifier.uri	http://elib.uni-stuttgart.de/handle/11682/3494	-
dc.identifier.uri	http://dx.doi.org/10.18419/opus-3477	-
dc.description.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.	en
dc.description.abstract	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.	de
dc.language.iso	en	de
dc.rights	info:eu-repo/semantics/openAccess	de
dc.subject.classification	Theoretische Informatik , Automatentheorie , Entscheidbarkeit	de
dc.subject.ddc	004	de
dc.subject.other	Monadische Logik zweiter Stufe , Syntaktische Halbgruppe	de
dc.subject.other	theoretical computer science , automata theory , monadic second-order logic, decidability , syntactic semigroup	en
dc.title	Formal language theory of logic fragments	en
dc.title.alternative	Formalsprachliche Theorie der Logikfragmente	de
dc.type	doctoralThesis	de
dc.date.updated	2015-01-28	de
ubs.dateAccepted	2014-08-28	de
ubs.fakultaet	Fakultät Informatik, Elektrotechnik und Informationstechnik	de
ubs.institut	Institut für Formale Methoden der Informatik	de
ubs.opusid	9783	de
ubs.publikation.typ	Dissertation	de
ubs.thesis.grantor	Fakultät Informatik, Elektrotechnik und Informationstechnik	de
Enthalten in den Sammlungen:	05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Dateien zu dieser Ressource:

Datei	Beschreibung	Größe	Format
diss_druckversion_2014_12_19_veroeffentlichungsversion.pdf		1,74 MB	Adobe PDF	Öffnen/Anzeigen

Zur Kurzanzeige

Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.

Universität Stuttgart

OPUS - Online Publikationen der Universität Stuttgart