17 found
Sort by:
  1. Erich Grädel & Jouko Väänänen (2013). Dependence and Independence. 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. (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  2. John Baldwin, Lev Beklemishev, Anuj Dawar, Mirna Dzamonja, David Evans, Erich Grädel, Denis Hirschfeldt, Hannes Leitgeb, Roger Maddux & Grigori Mints (2008). Vassar College, 124 Raymond Avenue, Poughkeepsie, Ny 12604, Usa. In a Review, a Reference “Jsl Xliii 148,” for Example, Refers Either to the Publication Reviewed on Page 148 of Volume 43 of the Journal, or to the Review Itself (Which Contains Full Bibliographical Information for the Reviewed Publication). Analogously, a Reference “Bsl VII 376” Refers to the Review Beginning on Page 376 in Volume 7 of This Bulletin, Or. [REVIEW] Bulletin of Symbolic Logic 14 (1).
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  3. Anuj Dawar Beklemishev, Mirna Dzamonja, David Evans, Erich Grädel, Denis Hirschfeldt, Hannes Leitgeb, Roger Maddux, Grigori Mints, Volker Peckhaus & Sławomir Solecki (2008). Vassar College, 124 Raymond Avenue, Poughkeepsie, Ny 12604, Usa. In a Review, a Reference “Jsl Xliii 148,” for Example, Refers Either to the Publication Reviewed on Page 148 of Volume 43 of the Journal, or to the Review Itself (Which Contains Full Bibliographical Information for the Reviewed Publication). Analogously, a Reference “Bsl VII 376” Refers to the Review Beginning on Page 376 in Volume 7 of This Bulletin, Or. [REVIEW] Bulletin of Symbolic Logic 14 (4).
    Direct download  
     
    My bibliography  
     
    Export citation  
  4. Erich Grädel, Phokion Kolaitis, Libkin G., Marx Leonid, Spencer Maarten, Vardi Joel, Y. Moshe, Yde Venema & Scott Weinstein (2007). Finite Model Theory and its Applications. Springer.
    This book gives a comprehensive overview of central themes of finite model theory – expressive power, descriptive complexity, and zero-one laws – together with selected applications relating to database theory and artificial intelligence, especially constraint databases and constraint satisfaction problems. The final chapter provides a concise modern introduction to modal logic, emphasizing the continuity in spirit and technique with finite model theory. This underlying spirit involves the use of various fragments of and hierarchies within first-order, second-order, fixed-point, and infinitary logics (...)
    Translate to English
    | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  5. Mirna Dzamonja, David M. Evans, Erich Grädel, Geoffrey P. Hellman, Denis Hirschfeldt, Julia Knight, Michael C. Laskowski, Roger Maddux, Volker Peckhaus & Wolfram Pohlers (2005). Books to Asl, Box 742, Vassar College, 124 Raymond Avenue, Poughkeepsie, Ny 12604, Usa. In a Review, a Reference “Jsl Xliii 148,” for Example, Refers Either to the Publication Reviewed on Page 148 of Volume 43 of the Journal, or to the Review Itself (Which Contains Full Bibliographical Information for the Reviewed Publication). Analogously, a Reference. [REVIEW] Bulletin of Symbolic Logic 11 (2).
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  6. Mirna Dzamonja, David M. Evans, Erich Gradel, Geoffrey P. Hellman, Denis Hirschfeldt, Julia Knight, Michael C. Laskowski, Roger Maddux, Volker Peckhaus & Wolfram Pohlers (2005). The Bulletin of Symbolic Logic Volume 11, Number 2, June 2005. Bulletin of Symbolic Logic 11 (2).
     
    My bibliography  
     
    Export citation  
  7. David M. Evans, Erich Grädel, Geoffrey P. Hellman, Denis Hirschfeldt, Thomas J. Jech, Julia Knight, Michael C. Laskowski, Volker Peckhaus, Wolfram Pohlers & Sławomir Solecki (2005). Vassar College, 124 Raymond Avenue, Poughkeepsie, Ny 12604, Usa. In a Review, a Reference “Jsl Xliii 148,” for Example, Refers Either to the Publication Reviewed on Page 148 of Volume 43 of the Journal, or to the Review Itself (Which Contains Full Bibliographical Information for the Reviewed Publication). Analogously, a Reference “Bsl VII 376” Refers to the Review Beginning on Page 376 in Volume 7 of This Bulletin, Or. [REVIEW] Bulletin of Symbolic Logic 11 (1):37.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  8. Erich Grädel (2003). 9th Workshop on Logic, Language, Information and Computation (Wollic'2002). Bulletin of Symbolic Logic 9 (1).
    Direct download  
     
    My bibliography  
     
    Export citation  
  9. Erich Grädel (1999). On the Restraining Power of Guards. Journal of Symbolic Logic 64 (4):1719-1742.
    Guarded fragments of first-order logic were recently introduced by Andreka, van Benthem and Nemeti; they consist of relational first-order formulae whose quantifiers are appropriately relativized by atoms. These fragments are interesting because they extend in a natural way many propositional modal logics, because they have useful model-theoretic properties and especially because they are decidable classes that avoid the usual syntactic restrictions (on the arity of relation symbols, the quantifier pattern or the number of variables) of almost all other known decidable (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  10. Erich Grädel, Martin Otto & Eric Rosen (1999). Undecidability Results on Two-Variable Logics. Archive for Mathematical Logic 38 (4-5):313-354.
    It is a classical result of Mortimer that $L^2$ , first-order logic with two variables, is decidable for satisfiability. We show that going beyond $L^2$ by adding any one of the following leads to an undecidable logic:– very weak forms of recursion, viz.¶(i) transitive closure operations¶(ii) (restricted) monadic fixed-point operations¶– weak access to cardinalities, through the Härtig (or equicardinality) quantifier¶– a choice construct known as Hilbert's $\epsilon$ -operator.In fact all these extensions of $L^2$ prove to be undecidable both for satisfiability, (...)
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  11. Erich Gradel & Eric Rosen (1999). On Preservation Theorems for Two-Variable Logic. Mathematical Logic Quarterly 45 (3):315-325.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  12. Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi (1997). On the Decision Problem for Two-Variable First-Order Logic. Bulletin of Symbolic Logic 3 (1):53-69.
    We identify the computational complexity of the satisfiability problem for FO 2 , the fragment of first-order logic consisting of all relational first-order sentences with at most two distinct variables. Although this fragment was shown to be decidable a long time ago, the computational complexity of its decision problem has not been pinpointed so far. In 1975 Mortimer proved that FO 2 has the finite-model property, which means that if an FO 2 -sentence is satisfiable, then it has a finite (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  13. Erich Grädel & Gregory L. McColm (1996). Hierarchies in Transitive Closure Logic, Stratified Datalog and Infinitary Logic. Annals of Pure and Applied Logic 77 (2):169-199.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  14. Sanjeev Arora, Matthias Baaz, Lenore Blum, Patrick Dehornoy, Solomon Feferman, Moti Gitik, Erich Grädel, Yuri Gurevich, Serge Grigorieff & David Harel (1995). Clermont-Ferrand, France, July 21–30, 1994. Bulletin of Symbolic Logic 1 (2).
    Direct download  
     
    My bibliography  
     
    Export citation  
  15. Erich Grädel & Yuri Gurevich (1995). Tailoring Recursion for Complexity. Journal of Symbolic Logic 60 (3):952-969.
    We design functional algebras that characterize various complexity classes of global functions. For this purpose, classical schemata from recursion theory are tailored for capturing complexity. In particular we present a functional analog of first-order logic and describe algebras of the functions computable in nondeterministic logarithmic space, deterministic and nondeterministic polynomial time, and for the functions computable by AC 1 -circuits.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  16. Erich Grädel (1990). Satisfiability of Formulae with One ∀ is Decidable in Exponential Time. Archive for Mathematical Logic 29 (4):265-276.
    In first order logic without equality, but with arbitrary relations and functions the ∃*∀∃* class is the unique maximal solvable prefix class. We show that the satisfiability problem for this class is decidable in deterministic exponential time The result is established by a structural analysis of a particular infinite subset of the Herbrand universe and by a polynomial space bounded alternating procedure.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  17. Erich Grädel (1989). Dominoes and the Complexity of Subclasses of Logical Theories. Annals of Pure and Applied Logic 43 (1):1-30.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation