Switch to: Citations

Add references

You must login to add references.
  1. Dependence and Independence.Erich Grädel & Jouko Väänänen - 2013 - Studia Logica 101 (2):399-410.
    We introduce an atomic formula ${\vec{y} \bot_{\vec{x}}\vec{z}}$ intuitively saying that the variables ${\vec{y}}$ are independent from the variables ${\vec{z}}$ if the variables ${\vec{x}}$ are kept constant. We contrast this with dependence logic ${\mathcal{D}}$ based on the atomic formula = ${(\vec{x}, \vec{y})}$ , actually equivalent to ${\vec{y} \bot_{\vec{x}}\vec{y}}$ , saying that the variables ${\vec{y}}$ are totally determined by the variables ${\vec{x}}$ . We show that ${\vec{y} \bot_{\vec{x}}\vec{z}}$ gives rise to a natural logic capable of formalizing basic intuitions about independence and dependence. (...)
    Download  
     
    Export citation  
     
    Bookmark   49 citations  
  • Lindström Quantifiers and Leaf Language Definability.Hans J. Burtschick & Heribert Vollmer - 1998 - International Journal of Foundations of Computer Science 9 (3):277--294.
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • On definability in dependence logic.Juha Kontinen & Jouko Väänänen - 2009 - Journal of Logic, Language and Information 18 (3):317-332.
    We study the expressive power of open formulas of dependence logic introduced in Väänänen [Dependence logic (Vol. 70 of London Mathematical Society Student Texts), 2007]. In particular, we answer a question raised by Wilfrid Hodges: how to characterize the sets of teams definable by means of identity only in dependence logic, or equivalently in independence friendly logic.
    Download  
     
    Export citation  
     
    Bookmark   35 citations  
  • On second-order generalized quantifiers and finite structures.Anders Andersson - 2002 - Annals of Pure and Applied Logic 115 (1--3):1--32.
    We consider the expressive power of second - order generalized quantifiers on finite structures, especially with respect to the types of the quantifiers. We show that on finite structures with at most binary relations, there are very powerful second - order generalized quantifiers, even of the simplest possible type. More precisely, if a logic is countable and satisfies some weak closure conditions, then there is a generalized second - order quantifier which is monadic, unary and simple, and a uniformly obtained (...)
    Download  
     
    Export citation  
     
    Bookmark   7 citations  
  • (1 other version)Some remarks on infinitely long formulas.L. Henkin - 1961 - Journal of Symbolic Logic 30 (1):167--183.
    Download  
     
    Export citation  
     
    Bookmark   102 citations  
  • First order predicate logic with generalized quantifiers.Per Lindström - 1966 - Theoria 32 (3):186--195.
    Download  
     
    Export citation  
     
    Bookmark   180 citations  
  • Inclusion and exclusion dependencies in team semantics—on some logics of imperfect information.Pietro Galliani - 2012 - Annals of Pure and Applied Logic 163 (1):68-84.
    Download  
     
    Export citation  
     
    Bookmark   40 citations  
  • The Hierarchy Theorem for Second Order Generalized Quantifiers.Juha Kontinen - 2006 - Journal of Symbolic Logic 71 (1):188 - 202.
    We study definability of second order generalized quantifiers on finite structures. Our main result says that for every second order type t there exists a second order generalized quantifier of type t which is not definable in the extension of second order logic by all second order generalized quantifiers of types lower than t.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Definability of second order generalized quantifiers.Juha Kontinen - 2010 - Archive for Mathematical Logic 49 (3):379-398.
    We study second order generalized quantifiers on finite structures. One starting point of this research has been the notion of definability of Lindström quantifiers. We formulate an analogous notion for second order generalized quantifiers and study definability of second order generalized quantifiers in terms of Lindström quantifiers.
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • Introduction to Circuit Complexity: A Uniform Approach.Heribert Vollmer - 1999 - Springer Verlag.
    An advanced textbook giving a broad, modern view of the computational complexity theory of boolean circuits, with extensive references, for theoretical computer scientists and mathematicians.
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • Characterizing Quantifier Extensions of Dependence Logic.Fredrik Engström & Juha Kontinen - 2013 - Journal of Symbolic Logic 78 (1):307-316.
    We characterize the expressive power of extensions of Dependence Logic and Independence Logic by monotone generalized quanti ers in terms of quanti er extensions of existential second-order logic.
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • Generalized Quantifiers in Dependence Logic.Fredrik Engström - 2012 - Journal of Logic, Language and Information 21 (3):299-324.
    We introduce generalized quantifiers, as defined in Tarskian semantics by Mostowski and Lindström, in logics whose semantics is based on teams instead of assignments, e.g., IF-logic and Dependence logic. Both the monotone and the non-monotone case is considered. It is argued that to handle quantifier scope dependencies of generalized quantifiers in a satisfying way the dependence atom in Dependence logic is not well suited and that the multivalued dependence atom is a better choice. This atom is in fact definably equivalent (...)
    Download  
     
    Export citation  
     
    Bookmark   13 citations  
  • From if to bi.Samson Abramsky & Jouko Väänänen - 2009 - Synthese 167 (2):207 - 230.
    We take a fresh look at the logics of informational dependence and independence of Hintikka and Sandu and Väänänen, and their compositional semantics due to Hodges. We show how Hodges’ semantics can be seen as a special case of a general construction, which provides a context for a useful completeness theorem with respect to a wider class of models. We shed some new light on each aspect of the logic. We show that the natural propositional logic carried by the semantics (...)
    Download  
     
    Export citation  
     
    Bookmark   31 citations  
  • Complexity Results for Modal Dependence Logic.Peter Lohmann & Heribert Vollmer - 2013 - Studia Logica 101 (2):343-366.
    Modal dependence logic was introduced recently by Väänänen. It enhances the basic modal language by an operator = (). For propositional variables p 1, . . . , p n , = (p 1, . . . , p n-1, p n ) intuitively states that the value of p n is determined by those of p 1, . . . , p n-1. Sevenster (J. Logic and Computation, 2009) showed that satisfiability for modal dependence logic is complete for nondeterministic (...)
    Download  
     
    Export citation  
     
    Bookmark   9 citations  
  • Expressing Second-order Sentences in Intuitionistic Dependence Logic.Fan Yang - 2013 - Studia Logica 101 (2):323-342.
    Intuitionistic dependence logic was introduced by Abramsky and Väänänen [1] as a variant of dependence logic under a general construction of Hodges’ (trump) team semantics. It was proven that there is a translation from intuitionistic dependence logic sentences into second order logic sentences. In this paper, we prove that the other direction is also true, therefore intuitionistic dependence logic is equivalent to second order logic on the level of sentences.
    Download  
     
    Export citation  
     
    Bookmark   8 citations  
  • Definability of Second Order Generalized Quantifiers.Juha Kontinen - 2004 - Dissertation,
    We study second order generalized quantifiers on finite structures. One starting point of this research has been the notion of definability of Lindström quantifiers. We formulate an analogous notion for second order generalized quantifiers and study definability of second order generalized quantifiers in terms of Lindström quantifiers.
    Download  
     
    Export citation  
     
    Bookmark   4 citations