Approaches to Finite Variable Dependence Expressiveness and Computational Complexity

The originality of this thesis has been checked using the Turnitin OriginalityCheck service in accordance with the quality management system of the University of Tampere. In this thesis we study computational aspects, expressive power and model-theoretic properties of fragments of various logics that are suitable for modeling diverse forms of variable dependence. In particular, we consider fragments of independence-friendly logic of Hintikka and Sandu, dependence logic of Väänä-nen, and first-order logic enriched with variants of partially-ordered connectives of Sandu and Väänänen closely related to the narrow Henkin quantifiers of Blass and Gurevich. Furthermore, we consider a novel variant of dependence logic called Boolean dependence logic. The thesis consists of two principal chapters: Chapters 3 and 4. In Chapter 3 the focus is on the computational complexity and expressive power of finite variable fragments of independence-friendly logic and dependence logic. The main result of the chapter is the undecidability of the satisfiability problem fo