
On the Complexity of Modal Logic Variants and their Fragments
Cuvillier Verlag eBooks
Published on 15. November 2011
148 pages
978-3-7369-3929-5 (ISBN)
System requirements
for PDF without DRM
E-Book Single Licence
You are acquiring a single user licence for this eBook, which you might not transfer. [L]
Available for download
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
The automatic verification of computer programs is an important step in software engineering. In this regard temporal logics have been invented as an extension of modal logic which itself is an extension of propositional logic. Therefore, one may call them \emph{modal logic variants}.
The first part of this thesis will investigate the two temporal logics CTL and CTL* with respect to their model-checking and satisfiability problem. We will analyze the complexity of fragments of these problems by means of operator and Boolean function restrictions. There we will see for the satisfiability problem, how the operator fragments form a trichotomy and the Boolean fragments form a quartering. The model-checking problem for CTL is divided into three types: monotone, atomic negation, and positive fragments. Surprisingly, we will see that these three fragments are computationally equivalent. Furthermore, several prominent extensions of CTL will be visited and classified with respect to their Boolean and operator fragments.
In the second part we will concentrate on description logics which are modal logic extensions settled in the area of semantic web, databases, and artificial intelligence. These types of logics are used to express, and work on, large sets of data. Besides the usual satisfiability problems, we will work with some special kind of implication problem, which is called subsumption. We will see that these logics combine two very strong Boolean concepts, namely implication and conjunction, such that restricting large sets of Boolean functions do not reduce the complexity of the problems significantly.
More details
Language
English
Place of publication
Göttingen
Germany
File size
0,91 MB
ISBN-13
978-3-7369-3929-5 (9783736939295)
Schweitzer Classification
Other editions
Additional editions

Book
11/2011
1st Edition
Cuvillier Verlag
€24.35
Shipment within 10-15 days
Person
Author/originator
Content
- Intro
- Zusammenfassung
- Abstract
- Contents
- List of Figures
- Introduction
- Preliminaries
- Temporal Logic
- Description Logic
- Concluding Remarks
- Bibliography
- Index
System requirements
File format: PDF
Copy protection: without DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use the free software Adobe Reader, Adobe Digital Editions, or any other PDF viewer of your choice (see eBook Help).
- Tablet/Smartphone (Android; iOS): Install the free app Adobe Digital Editions or another reading app for eBooks, e.g., PocketBook (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook does not use copy protection or Digital Rights Management.
For more information, see our eBook Help page.