The optimal balance between decidability and expressiveness is a big problem of logical systems, in particular, of quantified epistemic logics (QELs). On the one hand, decidability is a very significant characteristic of logics that allows us to use such logics in the framework of artificial intelligence. On the other hand, QELs have important expressive capabilities that should not be lost when we construct decidable fragments of these logics. QELs are known to be much more expressive than first-order logics. One important (...) example of their extra expressive power is that they allow us to distinguish between de dicto and de re readings of epistemic sentences. It is clear that such capabilities should be preserved as much as possible in decidable fragments. In this paper, we consider extensions of QELs that include quantification over modalities. Denote this extensions by $$\hbox {Q}_{\Box }$$ Ls. $$\hbox {Q}_{\Box }$$ Ls allows us to make more subtle distinctions between de dicto and de re readings of epistemic sentences, and we also should keep these new features as much as possible in decidable fragments. It is known that there are not much interesting decidable QELs. The situation with $$\hbox {Q}_{\Box }$$ Ls is the same. But in recent years (after 2018), we have obtained a variety of decidable $$\hbox {Q}_{\Box }$$ Ls constructed in different ways. We distinguish between (1) the approach in which for every undecidable $$\hbox {Q}_{\Box }$$ L and for every variant of its decidable fragment, a specific proof is constructed, and (2) the approach in which a class of decidable $$\hbox {Q}_{\Box }$$ Ls is obtained using general tools and a uniform method for all $$\hbox {Q}_{\Box }$$ Ls of this class. In this paper, we compare the results of these approaches. (shrink)

The paper presents a family of propositional epistemic logics such that languages of these logics are extended by quantification over modal operators or over agents of knowledge and extended by predicate symbols that take modal operators as arguments. Denote this family by \}\). There exist epistemic logics whose languages have the above mentioned properties :311–350, 1995; Lomuscio and Colombetti in Proceedings of ATAL 1996. Lecture Notes in Computer Science, vol 1193, pp 71–85, 1996). But these logics are obtained from first-order (...) modal logics, while a logic of \}\) can be regarded as a propositional multi-modal logic whose language includes quantifiers over modal operators and predicate symbols that take modal operators as arguments. Among the logics of \}\) there are logics with a syntactical distinction between two readings of epistemic sentences: de dicto and de re. We show the decidability of logics of \}\) with the help of the loosely guarded fragment of first-order logic. Namely, we generalize LGF to a higher-order decidable loosely guarded fragment. The latter fragment allows us to construct various decidable propositional epistemic logics with quantification over modal operators. The family of this logics coincides with \}\). There are decidable propositional logics such that these logics implicitly contain quantification over agents of knowledge, but languages of these logics are usual propositional epistemic languages without quantifiers and predicate symbols :345–378, 1993). Some logics of \}\) can be regarded as counterparts of logics defined in Grove and Halpern :345–378, 1993). We prove that the satisfiability problem for these logics of \}\) is Pspace-complete using their counterparts in Grove and Halpern :345–378, 1993). (shrink)

In the previous paper with a similar title :311–344, 2018), we presented a family of propositional epistemic logics whose languages are extended by two ingredients: by quantification over modal operators or over agents of knowledge and by predicate symbols that take modal operators as arguments. We denoted this family by \}\). The family \}\) is defined on the basis of a decidable higher-order generalization of the loosely guarded fragment of first-order logic. And since HO-LGF is decidable, we obtain the decidability (...) of logics of \}\). In this paper we construct an alternative family of decidable propositional epistemic logics whose languages include ingredients and. Denote this family by \}\). Now we will use another decidable fragment of first-order logic: the two variable fragment of first-order logic with two equivalence relations +2E) [the decidability of FO\+2E was proved in Kieroński and Otto :729–765, 2012)]. The families \}\) and \}\) differ in the expressive power. In particular, we exhibit classes of epistemic sentences considered in works on first-order modal logic demonstrating this difference. (shrink)

In this paper, we introduce a variant of second-order propositional modal logic interpreted on general (or Henkin) frames, \(SOPML^{\mathcal {H}}\), and present a decidable fragment of this logic, \(SOPML^{\mathcal {H}}_{dec}\), that preserves important expressive capabilities of \(SOPML^{\mathcal {H}}\). \(SOPML^{\mathcal {H}}_{dec}\) is defined as a _modal loosely guarded fragment_ of \(SOPML^{\mathcal {H}}\). We demonstrate the expressive power of \(SOPML^{\mathcal {H}}_{dec}\) using examples in which modal operators obtain (a) the epistemic interpretation, (b) the dynamic interpretation. \(SOPML^{\mathcal {H}}_{dec}\) partially satisfies the principle of (...) non-Fregean logic: two different _atomic_ propositions with the same truth value can have different contents. In \(SOPML^{\mathcal {H}}_{dec}\), we also define _relating connectives_ and show that the _weak Boethius’ Thesis_ built using these connectives is a valid formula of \(SOPML^{\mathcal {H}}_{dec}\). (shrink)

The guarded fragment (GF) was introduced by Andréka, van Benthem and Németi as a fragment of first order logic which combines a great expressive power with nice, modal behavior. It consists of relational first order formulas whose quantifiers are relativized by atoms in a certain way. Slightly generalizing the admissible relativizations yields the packed fragment (PF). In this paper we investigate interpolation and definability in these fragments. We first show that the interpolation property of first order logic fails in restriction (...) to GF and PF. However, each of these fragments turns out to have an alternative interpolation property that closely resembles the interpolation property usually studied in modal logic. These results are strong enough to entail the Beth definability property for GF and PF. Even better, every guarded or packed finite variable fragment has the Beth property. For interpolation, we characterize exactly which finite variable fragments of GF and PF enjoy this property. (shrink)

We prove decidability of satisfiability of sentences of the monodic packed fragment of first-order temporal logic with equality and connectives Until and Since, in models with various flows of time and domains of arbitrary cardinality. We also prove decidability over models with finite domains, over flows of time including the real order.

We provide a canonical construction of conformal covers for finite hypergraphs and present two immediate applications to the finite model theory of relational structures. In the setting of relational structures, conformal covers serve to construct guarded bisimilar companion structures that avoid all incidental Gaifman cliques-thus serving as a partial analogue in finite model theory for the usually infinite guarded unravellings. In hypergraph theoretic terms, we show that every finite hypergraph admits a bisimilar cover by a finite conformal hypergraph. In terms (...) of relational structures, we show that every finite relational structure admits a guarded bisimilar cover by a finite structure whose Gaifman cliques are guarded. One of our applications answers an open question about a clique constrained strengthening of the extension property for partial automorphisms (EPPA) of Hrushovski, Herwig and Lascar. A second application provides an alternative proof of the finite model property (FMP) for the clique guarded fragment of first-order logic CGF, by reducing (finite) satisfiability in CGF to (finite) satisfiability in the guarded fragment, GF. (shrink)

We show that the satisfiability problem for the monodic guarded, loosely guarded, and packed fragments of first-order temporal logic with equality is 2Exptime-complete for structures with arbitrary first-order domains, over linear time, dense linear time, rational number time, and some other classes of linear flows of time. We then show that for structures with finite first-order domains, these fragments are also 2Exptime-complete over real number time and hence over most of the commonly used linear flows of time, including the natural (...) numbers, integers, rationals, and any first-order definable class of linear flows of time. (shrink)