Computational properties of the logic of partial quasiary predicates
It is proved that Church theorem and Trakhtenbrot theorem are true for the logic of quasiary predicates.
We present a simple proof of Thrakhtenbrot's theorem for the classical predicate logic in the language with only three individual variables. Both forms of Thrakhtenbrot's theorem are established: we prove that the classical predicate logic QCL over finite domains is not recursively enumerable in the language with only three individual variables and that the set of theorems of QCL over arbitrary domains and the set of non-theorems of QCL over finite domains, in the language with only three individual variables, form a recursively inseparable pair of recursively enumerable sets. The techniques used here can be generalised to obtain similar results for non-classical predicate logics with further restrictions on their vocabularies.
It is well-known that every quantied modal logic complete with respect to a first-order definable class of Kripke frames is recursively enumerable. Numerous examples are also known of natural quantied modal logics complete with respect to a class of frames dened by an essentially second-order condition which are not recursively enumerable. It is not, however, known if these examples are instances of a pattern, i.e., whether every recursively enumerable, Kripke complete quantied modal logic can be characterized by a first-order definable class of frames. While the question remains open for normal logics, we show that, in the context of quasi-normal logics, this is not so, by exhibiting an example of a recursively enumerable, Kripke complete quasi-normal logic that is not complete with respect to any first-order definable class of (pointed) frames.
We investigate the relationship between recursive enumerability and elementary frame deﬁnability in ﬁrst-order predicate modal logic. On the one hand, it is wellknown that every ﬁrst-order predicate modal logic complete with respect to an elementary class of Kripke frames, i.e., a class of frames deﬁnable by a classical ﬁrst-order formula, is recursively enumerable. On the other, numerous examples are known of predicate modal logics, based on “natural” propositional modal logics with essentially second-order Kripke semantics, that are either not recursively enumerable or Kripke incomplete. This raises the question of whether every Kripke complete, recursively enumerable predicate modal logic can be characterized by an elementary class of Kripke frames. We answer this question in the negative, by constructing a normal predicate modal logic which is Kripke complete, recursively enumerable, but not complete with respect to an elementary class of frames. We also present an example of a normal predicate modal logic that is recursively enumerable, Kripke complete, and not complete with respect to an elementary class of rooted frames, but is complete with respect to an elementary class of frames that are not rooted.
We investigate the complexity of satisfiability for finite-variable fragments of propositional dynamic logics (PDLs). We consider three formalisms belonging to three representative complexity classes, broadly understood—regular PDL, which is EXPTIME-complete; PDL with intersection, which is 2EXPTIME-complete; and PDL with parallel composition, which is undecidable. We show that, for each of these logics, the complexity of satisfiability remains unchanged even if we only allow as inputs formulas built solely out of propositional constants, i.e. without propositional variables. Moreover, we show that this is a consequence of the richness of the expressive power of variable-free fragments: for all the logics we consider, such fragments are as semantically expressive as entire logics. We conjecture that this is representative of PDL-style, as well as closely related, logics.
Modal logics, both propositional and predicate, have been used in computer science since the late 1970s. One of the most important properties of modal logics of relevance to their applications in computer science is the complexity of their satisﬁability problem. The complexity of satisﬁability for modal logics is rather high: it ranges from NP-complete to undecidable for propositional logics and is undecidable for predicate logics. This has, for a long time, motivated research in drawing the borderline between tractable and intractable fragments of propositional modal logics as well as between decidable and undecidable fragments of predicate modal logics. In the present thesis, we investigate some very natural restrictions on the languages of propositional and predicate modal logics and show that placing those restrictions does not decrease complexity of satisﬁability. For propositional languages, we consider restricting the number of propositional variables allowed in the construction of formulas, while for predicate languages, we consider restricting the number of individual variables as well as the number and arity of predicate letters allowed in the construction of formulas. We develop original techniques, which build on and develop the techniques known from the literature, for proving that satisﬁability for a ﬁnite-variable fragment of a propositional modal logic is as computationally hard as satisﬁability for the logic in the full language and adapt those techniques to predicate modal logics and prove undecidability of fragments of such logics in the language with a ﬁnite number of unary predicate letters as well as restrictions on the number of individual variables. The thesis is based on four articles published or accepted for publication. They concern propositional dynamic logics, propositional branchingand alternating-time temporal logics, propositional logics of symmetric rela tions, and ﬁrst-order predicate modal and intuitionistic logics. In all cases, we identify the “minimal,” with regard to the criteria mentioned above, fragments whose satisﬁability is as computationally hard as satisﬁability for the entire logic.
In this paper we prove the finite model property and decidability of a family of pretrasitive modal logics of finite height. We construct special partitions (filtrations) of pretransitive frames of finite height, which implies the finite model property and decidability of their modal logics.
Filtration is a standard tool for establishing the finite model property of modal logics. We consider logics and classes of frames that admit filtration, and identify some operations on them that preserve this property. In particular, the operation of adding the inverse or the transitive closure of a relation is shown to be safe in this sense. These results are then used to prove that every regular grammar logic with converse admits filtration. We present filtration constructions for right-linear and left-linear grammar logics. We also give a simple example of a grammar modal logic that is undecidable and hence does not admit filtration.