By Edith Spaan

It is a doctoral dissertation of Edith Spaan lower than the supervision of prof. Johan van Benthem.

Show description

Read or Download Complexity of Modal Logics [PhD Thesis] PDF

Best logic books

Proof Theory (Dover Books on Mathematics) (2nd Edition)

This accomplished monograph is a cornerstone within the zone of mathematical common sense and similar fields. targeting Gentzen-type facts idea, the e-book provides a close evaluate of artistic works by the writer and different 20th-century logicians that includes purposes of evidence conception to good judgment in addition to different components of arithmetic.

The Phonological Spectrum, Volume 1: Segmental Structure

The 2 volumes of the Phonological Spectrum target at giving a accomplished evaluation of present advancements in phonological conception, by way of supplying a couple of papers in several components of present theorizing which contemplate specific difficulties from varied angles. quantity I is worried with segmental constitution, and makes a speciality of nasality, voicing and different laryngeal gains, in addition to segmental timing.

Mathematical Thought: An Introduction to the Philosophy of Mathematics

In contributing a foreword to this publication i'm complying with a want my husband expressed a couple of days sooner than his dying. He had accomplished the manuscript of this paintings, that could be thought of a better half quantity to his publication Formal tools. the duty of seeing it during the press used to be undertaken by way of Mr. J. J.

Fuzzy Logic - Algorithms, Techniques and Implementations

The aim of this publication is to introduce Hybrid Algorithms, ideas, and Implementations of Fuzzy common sense. The publication contains 13 chapters highlighting types and rules of fuzzy common sense and matters on its ideas and implementations. The meant readers of this e-book are engineers, researchers, and graduate scholars attracted to fuzzy good judgment structures.

Extra resources for Complexity of Modal Logics [PhD Thesis]

Example text

First suppose that 0! consists of two elements, say a and 6. 6, © aGn T a satisfiability is polynomial time reducible to T a ® satisfiability. By the previous section, T a ® T\> satisfiability is in NP, and thus © a€n T a satisfiability is in NP as well. Finally, suppose that 0! contains at least three elements. Since we are not in case N, it follows that for all a £ fi, is not a skeleton subframe of T a. Furthermore, since we are not in case A, we know that / \ is not a skeleton subframe of T a.

Then satisfiability is PSP ACE-hard. 1. We will prove the analog for the general join of uni-modal logics. There is no reason why there shouldn’t exist such a theorem for multi­ modal logics. However, there are very many cases which force PSPACE hardness, and we haven’t managed to obtain a complete characterization. 1. To see why the situation is more complex if we consider the join of multi-modal logics, look at the following example: CHAPTER 3. THE COMPLEXITY OF THE JOIN 46 Q = {{a, a'}, {&, 6'}}, and .

E. for a £ {1,2}, either all three worlds are a reflexive, or all three worlds are a irreflexive. Next, we want the constructed tree to be an T \ 0 T 2 subframe. This is not true for every frame F: Suppose for instance that wqR\W i , and that T \ consists of the closure under disjoint union of the frame •—~ . Then the tree constructed from F is not an T \ 0 T 2 subframe, as identification of w0 and wi worlds leads to arbitrarily long Ri paths. This problem can be avoided by requiring that Wo has no non-reflexive Ri edges, and wt and wr have no non-reflexive R 2 edges or vice versa.

Download PDF sample

Rated 4.27 of 5 – based on 18 votes