This dissertation studies the relative expressive power and properties of several fixpoint and second-order logics. We use the term fixpoint logic in a broad sense, referring to any logic which can encode some type of recursion, iteration or repetition. Our main objective is to systematically identify several important logics as precise fragments of other well-known logics. In order to accomplish this task, we develop automata-theoretic tools to analyze these fragments. The results of this dissertation provide new insight on the relationship of fixpoint and second-order logic and provides further evidence of the successful logic-automata connection.
We introduce a new class of parity automata which, on trees, captures the expressive power of weak chain logic. This logic is a variant of monadic second-order logic which quantifies over finite chains. Using this new tool, we show that the bisimulation-invariant fragment of weak chain logic is equivalent to propositional dynamic logic.
It is well known that Propositional Dynamic Logic (PDL) can be seen as a fragment of the modal \(\mu\)-calculus. In this paper we provide an exact syntactic characterization of the fragments of the \(\mu\)-calculus that correspond to PDL and to test-free PDL. In addition we give automata-theoretic characterizations for PDL, with and without tests, which shed light on the relation between these logics and the modal \(\mu\)-calculus and provide a new framework for the development of the theory of PDL.
We prove that the bisimulation-invariant fragment of weak monadic second-order logic (WMSO) is equivalent to the fragment of the modal \(\mu\)-calculus where the application of the least fixpoint operator \(\mu p.\varphi\) is restricted to formulas \(\varphi\) that are continuous in p. Our proof is automata-theoretic in nature; in particular, we introduce a class of automata characterizing the expressive power of WMSO over tree models of arbitrary branching degree. The transition map of these automata is defined in terms of a logic \(FOE^\infty_1\) that is the extension of first-order logic with a generalized quantifier \(\exists^\infty\), where \(\exists^\infty x.\varphi\) means that there are infinitely many objects satisfying \(\varphi\). An important part of our work consists of a model-theoretic analysis of \(FOE^\infty_1\).
Three important results about the expressivity of a modal logic L are the Characterization Theorem (that identifies a modal logic L as a fragment of a better known logic), the Definability Theorem (that provides conditions under which a class of L-models can be defined by a formula or a set of formulas of L), and the Separation Theorem (that provides conditions under which two disjoint classes of L-models can be separated by a class definable in L). We provide general conditions under which these results can be established for a given choice of model class and modal language whose expressivity is below first order logic. Besides some basic constraints that most modal logics easily satisfy, the fundamental condition that we require is that the class of \(\omega\)-saturated models in question has the Hennessy-Milner property with respect to the notion of observational equivalence under consideration. Given that the Characterization, finability and Separation theorems are among the cornerstones in the model theory of L, this property can be seen as a test that identifies the adequate notion of observational equivalence for a particular modal logic.
In epistemic logic, dynamic operators describe the evolution of the knowledge of participating agents through communication, one of the most basic forms of communication being public announcement. Semantically, dynamic operators correspond to transformations of the underlying model. While metatheoretic results on dynamic epistemic logic so far are largely limited to the setting of Kripke models, there is evident interest in extending its scope to non-relational modalities capturing, e.g., uncertainty or collaboration. We develop a generic framework for non-relational dynamic logic by adding dynamic operators to coalgebraic logic. We discuss a range of examples and establish basic results including bisimulation invariance, complexity, and a small model property.
Satisfiability problem for modal logic K augmented with quantifier-free Presburger and regularity constraints (EML) is known to be PSPACE-complete. In this paper, we consider its extension with nonregular constraints and more specifically those expressed by visibly pushdown languages (VPL). This class of languages is known to behave nicely, in particular when combined with Propositional Dynamic Logic (PDL). By extending EML, we show that decidability is preserved if we allow at most one positive VPL at each modal depth. By contrast, the presence of two VPL-contraints at the same modal depth or the presence of a negative occurrence of a single VPL-constraint leads to undecidability. This contrasts with decidability of PDL augmented with VPL-constraints.
Memory logics is a family of modal logics whose semantics is specified in terms of relational models enriched with additional data structure to represent a memory. The logical language includes a collection of operations to access and modify the data structure. In this paper we study basic model properties of memory logics, and prove results concerning characterization, definability and interpolation. While the first two properties hold for all memory logics introduced in this article, interpolation fails in most cases.
Two important classic results about modal expressivity are the Characterization and Definability theorems. We develop a general theory for modal logics below first order (in terms of expressivity) which exposes the following result: Characterization and Definability theorems hold for every (reasonable) modal logic whose omega-saturated models have the Hennessy-Milner property. The results are presented in a general version which is relativized to classes of models.