Download Complexity of Modal Logics [PhD Thesis] by Edith Spaan PDF

By Edith Spaan

This can be a doctoral dissertation of Edith Spaan below the supervision of prof. Johan van Benthem.

Show description

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

Best logic books

An Introduction to Symbolic Logic and Its Applications

A transparent, entire, and rigorous therapy develops the topic from basic suggestions to the development and research of rather complicated logical languages. It then considers the applying of symbolic good judgment to the explanation and axiomatization of theories in arithmetic, physics, and biology.

Errors of Reasoning. Naturalizing the Logic of Inference

Error of Reasoning is the long-awaited continuation of the author's research of the good judgment of cognitive structures. the current concentration is the person human reasoner working below the stipulations and pressures of genuine lifestyles with capacities and assets the flora and fauna makes to be had to him.

Quanta, logic and spacetime

During this multiplied variation of Quanta, common sense and Spacetime, the logical base is significantly broadened and quantum-computational elements of the process are dropped at the fore. the 1st elements of this variation might certainly be considered as supplying a self-contained and logic-based starting place for — and an creation to — the company often called quantum computing.

Knowledge Representation and Reasoning Under Uncertainty: Logic at Work

This quantity relies at the foreign convention good judgment at paintings, held in Amsterdam, The Netherlands, in December 1992. The 14 papers during this quantity are chosen from 86 submissions and eight invited contributions and are all dedicated to wisdom illustration and reasoning lower than uncertainty, that are center problems with formal man made intelligence.

Additional resources for Complexity of Modal Logics [PhD Thesis]

Example text

The satisfiability problem for this class of frames is in NP. e. pO(^ )w }| \). We start by describing the form of the frames in T \ and T 2. 3 Let T \ and T 2 be two classes of uni-modal frames closed under disjoint union. If we are not in case I and A through F, then for some a £ {1,2}, we are in one of the following three cases: not skeleton subframe of T a not skeleton subframe of Ta • CY ct G •A • ; •— •> \• ; •— • • H • \ , * ** \ ) • • CY^^ ^_^0—^0 ^ 00 ^0 ^ ^ ^CY , CY } 9 ^CY J In the proof of the first requirement, we have seen that / \ m , and 9 + 2 „ are not skeleton subframes of T \ nor of T 2.

4 can be applied in cases A through F follows from the previous section. 4 with cr = abc, and F the following frame: c £)a 48 CHAPTER 3. 2. Let 0! be the set of indices a such that ^ is a skeleton subframe of T a. Since we are not in case I, it follows that |H'| > 2. 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.

It follows that we need DSPACE(s(n2) + (m — l)s(rc2)) = DSPACE(ms(n2)). On the other hand, the time that is needed is proportional to the number of queries multiplied by the time per query. It follows that we need DTIME(£(n2)£(n2)m_1) = DTIME(*(n2)m). For nondeterministic time classes, this proof does not go through, since in general these classes are not known to be closed under complementation. However, a slight variation of the construction above gives the wanted transfer result. Instead of computing whether a query belongs to 7Za, we guess the set of queries in lZa and verify that all these queries are indeed in 7Z^.

Download PDF sample

Rated 4.93 of 5 – based on 24 votes