Cookies help us deliver our services. By using our services, you agree to our use of cookies.

Cuvillier Verlag

Publications, Dissertations, Habilitations & Brochures.
International Specialist Publishing House for Science and Economy

Cuvillier Verlag

De En Es
Complexity and Expressivity of Dependence Logic Extensions

Hard Copy
EUR 19.80 EUR 18.81

E-book
EUR 13.86

Complexity and Expressivity of Dependence Logic Extensions (English shop)

Johannes Ebbing (Author)

Preview

Extract, PDF (81 KB)
Table of Contents, PDF (56 KB)

ISBN-13 (Hard Copy) 9783954046294
ISBN-13 (eBook) 9783736946293
Language English
Page Number 114
Lamination of Cover matt
Edition 1. Aufl.
Publication Place Göttingen
Place of Dissertation Hannover
Publication Date 2014-02-06
General Categorization Dissertation
Departments Informatics
Keywords Logic, Dependence Logic, Complexity Theory
Description

Dependence Logic (D) wurde 2007 von Jouko Väänänen erstmals vorgestellt. Hierbei handelte es sich um eine Logik, welche die Prädikatenlogik der ersten Stufe um das sogenannte dependence Atom (in Zeichen =(t_1,…,t_n)) erweitert. Es ist erfüllt, wenn die funktionale Abhängigkeit des Terms t_n von den Termen t_1,…, t_n-1 gegeben ist, d.h. wenn t_n eine Funktion von t_1,…, t_n-1 ist. 2009 wurde eine modale Version der dependence Logik (MDL) von Abramsky und Väänänen erstmals vorgestellt.
In dieser Arbeit betrachten wir sowohl modale als sich die prädikatenlogische Variante.

In Kapitel 3 stellen wir die Erweiterungen der dependence Logik um die Quantoren M und ein Paritätsquantor.

Der Quantor M ist erfüllt, wenn mindestens die Hälfte aller Belegungen für die quantifizierte Variable wahr ist. Der Paritätsquantor wird wahr, wenn eine gerade Anzahl von Belegungen der quantifizierten Variablen wahr ist. In Kapitel 3 zeigen wir, dass dependence Logik erweitert um M mit der Hierarchie der Zählklassen PP (CH) übereinstimmt und dependence Logik erweitert um den Paritätsquantor mit der Komplexitätsklasse parityP.

Kapitel 4 beschäftigt sich mit erweiterter modalen dependence Logik (EMDL), welche auf der von Sevenster und Väänänen vorgestellten modalen dependence Logik beruht. Hierbei wird das dependence Atom =(p_1,…, p_n), welches in MDL nur auf atomare Propositionen p_1,…,p_n angewendet wird, durch ein neues dependence Atom ersetzt, welches auch modalligische Formeln beinhalten kann. Wir zeigen, dass die Komplexität des Modellprüfungsproblems sowie die Komplexität des Erfüllbarkeitsproblems nicht schwieriger sind, als die korrespondierenden Probleme auf der Logik MDL. Außerdem zeigen wir, dass es EMDL Formeln gibt, die nicht durch MDL Formeln abgebildet werden können.

In Kapitel 5 wird wieder eine Variante der prädikatenlogischen dependence Logik vorgestellt. Diese Boole’scher dependence Logik BD wird mit sogenannten partially ordered connectives verglichen, welche von Henkin vorgestellt wurden. Dabei wird gezeigt, dass die Logiken sowie ihre Fragmente äquivalent sind. Des Weiteren wird gezeigt, dass Boole’sche dependence Logik eine strikte Trennung zu ihren Logikfragmenten aufweist. Das heißt, dass es Formeln in einem Fragment der Logik gibt, die sich nicht in einem kleineren Fragment der Logik darstellen lassen.