Results for 'Ittai Gradel'

30 found
Order:
  1.  47
    For Specialists in Roman Religion C. Ando (Ed.): Roman Religion . (Edinburgh Readings on the Ancient World.) Pp. Xxii + 393, Maps, Ills. Edinburgh: Edinburgh University Press, 2003. Paper. ISBN: 0-7486-1566-0 (0-7486-1565-2 Hbk). [REVIEW]Ittai Gradel - 2005 - The Classical Review 55 (01):285-.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  2. 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. (...)
    Direct download (11 more)  
     
    Export citation  
     
    Bookmark   22 citations  
  3.  44
    On the Decision Problem for Two-Variable First-Order Logic.Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi - 1997 - 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 (10 more)  
     
    Export citation  
     
    Bookmark   26 citations  
  4. On the Restraining Power of Guards.Erich Grädel - 1999 - 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 (9 more)  
     
    Export citation  
     
    Bookmark   19 citations  
  5.  20
    Undecidability Results on Two-Variable Logics.Erich Grädel, Martin Otto & Eric Rosen - 1999 - 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, (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  6.  10
    On Preservation Theorems for Two-Variable Logic.Erich Gradel & Eric Rosen - 1999 - Mathematical Logic Quarterly 45 (3):315-325.
    We show that the existential preservation theorem fails for two-variable first-order logic FO2. It is known that for all k ≥ 3, FOk does not have an existential preservation theorem, so this settles the last open case, answering a question of Andreka, van Benthem, and Németi. In contrast, we prove that the homomorphism preservation theorem holds for FO2.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  7. Finite Model Theory and its Applications. Texts in Theoretical Computer Science.E. Grädel, P. G. Kolaitis, L. Libkin, M. Marx, J. Spencer & M. Y. Vardi - 2010 - Bulletin of Symbolic Logic 16 (3):406-407.
  8.  15
    Rank Logic is Dead, Long Live Rank Logic!Erich Grädel & Wied Pakusa - 2019 - Journal of Symbolic Logic 84 (1):54-87.
    Motivated by the search for a logic for polynomial time, we study rank logic which extends fixed-point logic with counting by operators that determine the rank of matrices over finite fields. WhileFPRcan express most of the known queries that separateFPCfromPtime, almost nothing was known about the limitations of its expressive power.In our first main result we show that the extensions ofFPCby rank operators over different prime fields are incomparable. This solves an open question posed by Dawar and Holm and also (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  9.  17
    Hierarchies in Transitive Closure Logic, Stratified Datalog and Infinitary Logic.Erich Grädel & Gregory L. McColm - 1996 - Annals of Pure and Applied Logic 77 (2):169-199.
    We establish a general hierarchy theorem for quantifier classes in the infinitary logic L∞ωωon finite structures. In particular, it is shown that no infinitary formula with bounded number of universal quantifiers can express the negation of a transitive closure.This implies the solution of several open problems in finite model theory: On finite structures, positive transitive closure logic is not closed under negation. More generally the hierarchy defined by interleaving negation and transitive closure operators is strict. This proves a conjecture of (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  10.  8
    Dominoes and the Complexity of Subclasses of Logical Theories.Erich Grädel - 1989 - Annals of Pure and Applied Logic 43 (1):1-30.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  11.  21
    Satisfiability of Formulae with One ∀ is Decidable in Exponential Time.Erich Grädel - 1990 - 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.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  12.  25
    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]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 - Bulletin of Symbolic Logic 11 (1):37.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  13.  18
    Tailoring Recursion for Complexity.Erich Grädel & Yuri Gurevich - 1995 - 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 (9 more)  
     
    Export citation  
     
    Bookmark  
  14. 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]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 - Bulletin of Symbolic Logic 11 (2).
     
    Export citation  
     
    Bookmark  
  15.  25
    0-1 Laws for Recursive Structures.E. Grädel & A. Malmström - 1999 - Archive for Mathematical Logic 38 (4-5):205-215.
    We discuss resource-bounded measures on the class of recursive structures and prove that with respect to such measures a random recursive structure is almost surely isomorphic to the unique countable model of the extension axioms.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  16.  13
    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]John Baldwin, Lev Beklemishev, Anuj Dawar, Mirna Dzamonja, David Evans, Erich Grädel, Denis Hirschfeldt, Hannes Leitgeb, Roger Maddux & Grigori Mints - 2008 - Bulletin of Symbolic Logic 14 (1).
    Direct download  
     
    Export citation  
     
    Bookmark  
  17.  9
    9th Workshop on Logic, Language, Information and Computation (Wollic'2002).Erich Grädel - 2003 - Bulletin of Symbolic Logic 9 (1):941-949.
  18. 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]Anuj Dawar Beklemishev, Mirna Dzamonja, David Evans, Erich Grädel, Denis Hirschfeldt, Hannes Leitgeb, Roger Maddux, Grigori Mints, Volker Peckhaus & Sławomir Solecki - 2008 - Bulletin of Symbolic Logic 14 (4).
     
    Export citation  
     
    Bookmark  
  19. The Bulletin of Symbolic Logic Volume 11, Number 2, June 2005.Mirna Dzamonja, David M. Evans, Erich Gradel, Geoffrey P. Hellman, Denis Hirschfeldt, Julia Knight, Michael C. Laskowski, Roger Maddux, Volker Peckhaus & Wolfram Pohlers - 2005 - Bulletin of Symbolic Logic 11 (2).
  20.  48
    Finite Model Theory and its Applications.Erich Grädel, Phokion Kolaitis, Libkin G., Marx Leonid, Spencer Maarten, Vardi Joel, Y. Moshe, Yde Venema & Scott Weinstein - 2007 - 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 (...)
    Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  21.  14
    A Second-Order System for Polytime Reasoning Based on Grädel's Theorem.Stephen Cook & Antonina Kolokolova - 2003 - Annals of Pure and Applied Logic 124 (1-3):193-231.
    We introduce a second-order system V1-Horn of bounded arithmetic formalizing polynomial-time reasoning, based on Grädel's 35) second-order Horn characterization of P. Our system has comprehension over P predicates , and only finitely many function symbols. Other systems of polynomial-time reasoning either allow induction on NP predicates , and hence are more powerful than our system , or use Cobham's theorem to introduce function symbols for all polynomial-time functions . We prove that our system is equivalent to QPV and Zambella's P-def. (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  22.  22
    Automata, Logics, and Infinite Games: A Guide to Current Research, Edited by Erich Grädel, Wolfgang Thomas, and Thomas Wilke, Lecture Notes in Computer Science, Vol. 2500 . Springer-Verlag, Berlin Heidelberg, 2002, Viii + 385 Pp. [REVIEW]David Janin - 2004 - Bulletin of Symbolic Logic 10 (1):114-115.
  23.  11
    Ittai Weinryb, The Bronze Object in the Middle Ages. Cambridge: Cambridge University Press, 2016. Pp. Xx, 298; Many Color Figures and 1 Map. $99.99. ISBN: 978-1-107-12361-8. [REVIEW]Gerhard Lutz - 2019 - Speculum 94 (2):602-6604.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  24.  9
    E. Grädel, P.G. Kolaitis, L. Libkin, M. Marx, J. Spencer, M.Y. Vardi, Y. Venema and S. Weinstein. Finite Model Theory and its Applications. Texts in Theoretical Computer Science. Springer, Berlin, 2007, Xiii + 437 Pp. [REVIEW]Stephan Kreutzer - 2010 - Bulletin of Symbolic Logic 16 (3):406-407.
  25.  36
    The Classical Decision Problem, Egon Börger, Erich Grädel, and Yuri Gurevich.Maarten Marx - 1999 - Journal of Logic, Language and Information 8 (4):478-481.
  26. A Companion to Dr. Zinkernagel's Conditions for Description. Translated From the Danish by Morris Gradel.Klaus-Henrik Jacobsen & Peter Zinkernagel - 1972
    No categories
     
    Export citation  
     
    Bookmark  
  27.  65
    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 (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  28.  15
    Spike Bucklow, The Riddle of the Image: The Secret Science of Medieval Art. London: Reaktion Books, 2014. Pp. 304; 3 Black-and-White and 50 Color Figures. £29. ISBN: 978-1-78023-294-2. [REVIEW]Ittai Weinryb - 2016 - Speculum 91 (4):1079-1080.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  29.  3
    Hildesheim Avant-Garde: Bronze, Columns, and Colonialism.Ittai Weinryb - 2018 - Speculum 93 (3):728-782.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  30. 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" Bsl VII 376" Refers to the Review Beginning on Page 376 in Volume 7 of This Bulletin, Or. [REVIEW]John Baldwin Lev Beklemishev Mima Dzamonja & David Evans Erich Gradel Denis - 2006 - Bulletin of Symbolic Logic 12 (2):290.
     
    Export citation  
     
    Bookmark