42 found
Sort by:
  1. Carlos Cotrini & Yuri Gurevich (2013). Transitive Primal Infon Logic. Review of Symbolic Logic 6 (2):281-304.
    Primal infon logic was introduced in 2009 in connection with access control. In addition to traditional logic constructs, it contains unary connectives p said indispensable in the intended access control applications. Propositional primal infon logic is decidable in linear time, yet suffices for many common access control scenarios. The most obvious limitation on its expressivity is the failure of the transitivity law for implication: \$$ \to \$$ and \$$ \to \$$ do not necessarily yield \$$ \to \$$. Here we introduce (...)
    No categories
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  2. Yuri Gurevich (2012). Foundational Analyses of Computation. In. In S. Barry Cooper (ed.), How the World Computes. 264--275.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  3. Yuri Gurevich & Grant Olney Passmore (2012). Impugning Randomness, Convincingly. Studia Logica 100 (1-2):193-222.
    John organized a state lottery and his wife won the main prize. You may feel that the event of her winning wasn’t particularly random, but how would you argue that in a fair court of law? Traditional probability theory does not even have the notion of random events. Algorithmic information theory does, but it is not applicable to real-world scenarios like the lottery one. We attempt to rectify that.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  4. Andreas Blass, Nachum Dershowitz & Yuri Gurevich (2009). When Are Two Algorithms the Same? Bulletin of Symbolic Logic 15 (2):145-168.
    People usually regard algorithms as more abstract than the programs that implement them. The natural way to formalize this idea is that algorithms are equivalence classes of programs with respect to a suitable equivalence relation. We argue that no such equivalence relation exists.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  5. Robert H. Gilman, Yuri Gurevich & Alexei Miasnikov (2009). A Geometric Zero-One Law. Journal of Symbolic Logic 74 (3):929-938.
    Each relational structure X has an associated Gaifman graph, which endows X with the properties of a graph. If x is an element of X, let $B_n (x)$ be the ball of radius n around x. Suppose that X is infinite, connected and of bounded degree. A first-order sentence ϕ in the language of X is almost surely true (resp. a. s. false) for finite substructures of X if for every x ∈ X, the fraction of substructures of $B_n (x)$ (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  6. Nachum Dershowitz & Yuri Gurevich (2008). A Natural Axiomatization of Computability and Proof of Church's Thesis. Bulletin of Symbolic Logic 14 (3):299-350.
    Church's Thesis asserts that the only numeric functions that can be calculated by effective means are the recursive ones, which are the same, extensionally, as the Turing-computable numeric functions. The Abstract State Machine Theorem states that every classical algorithm is behaviorally equivalent to an abstract state machine. This theorem presupposes three natural postulates about algorithmic computation. Here, we show that augmenting those postulates with an additional requirement regarding basic operations gives a natural axiomatization of computability and a proof of Church's (...)
    Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  7. Anjolina Grisi de Oliveira, Valéria de Paiva, Eli Ben-Sasson & Yuri Gurevich (2007). CSLI, Stanford, USA July 18–21, 2006. Bulletin of Symbolic Logic 13 (3).
    Direct download  
     
    My bibliography  
     
    Export citation  
  8. Gregory Cherlin, Alan Dow, Yuri Gurevich, Leo Harrington, Ulrich Kohlenbach, Phokion Kolaitis, Leonid Levin, Michael Makkai, Ralph McKenzie & Don Pigozzi (2004). University of Illinois at Chicago, Chicago, IL, June 1–4, 2003. Bulletin of Symbolic Logic 10 (1).
    Direct download  
     
    My bibliography  
     
    Export citation  
  9. Georg Gottlob, Yuri Gurevich, Dietmar Seipel & J. M. Turull-Torres (2004). Third International Symposium on Foundations of Information and Knowledge Systems (Foiks 2004). Bulletin of Symbolic Logic 10 (4).
    Direct download  
     
    My bibliography  
     
    Export citation  
  10. Andreas Blass & Yuri Gurevich (2003). Strong Extension Axioms and Shelah's Zero-One Law for Choiceless Polynomial Time. Journal of Symbolic Logic 68 (1):65-131.
    This paper developed from Shelah's proof of a zero-one law for the complexity class "choice-less polynomial time." defined by Shelah and the authors. We present a detailed proof of Shelah's result for graphs, and describe the extent of its generalizability to other sorts of structures. The extension axioms, which form the basis for earlier zero-one laws (for first-order logic, fixed-point logic, and finite-variable infinitary logic) are inadequate in the case of choiceless polynomial time; they must be replaced by what we (...)
    Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  11. Andreas Blass, Yuri Gurevich & Saharon Shelah (2002). On Polynomial Time Computation Over Unordered Structures. Journal of Symbolic Logic 67 (3):1093-1125.
    This paper is motivated by the question whether there exists a logic capturing polynomial time computation over unordered structures. We consider several algorithmic problems near the border of the known, logically defined complexity classes contained in polynomial time. We show that fixpoint logic plus counting is stronger than might be expected, in that it can express the existence of a complete matching in a bipartite graph. We revisit the known examples that separate polynomial time from fixpoint plus counting. We show (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  12. Anuj Dawar & Yuri Gurevich (2002). Fixed Point Logics. Bulletin of Symbolic Logic 8 (1):65-88.
    We consider fixed point logics, i.e., extensions of first order predicate logic with operators defining fixed points. A number of such operators, generalizing inductive definitions, have been studied in the context of finite model theory, including nondeterministic and alternating operators. We review results established in finite model theory, and also consider the expressive power of the resulting logics on infinite structures. In particular, we establish the relationship between inflationary and nondeterministic fixed point logics and second order logic, and we consider (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  13. Andreas Blass, Yuri Gurevich & Saharon Shelah (2001). Addendum to “Choiceless Polynomial Time”. Annals of Pure and Applied Logic 112 (1):117.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  14. Andreas Blass, Yuri Gurevich & Saharon Shelah (2001). Addendum to “Choiceless Polynomial Time”: Ann. Pure Appl. Logic 100 (1999) 141–187. Annals of Pure and Applied Logic 112 (1):117.
    No categories
     
    My bibliography  
     
    Export citation  
  15. Andreas Blass & Yuri Gurevich (2000). The Logic of Choice. Journal of Symbolic Logic 65 (3):1264-1310.
    The choice construct (choose x: φ(x)) is useful in software specifications. We study extensions of first-order logic with the choice construct. We prove some results about Hilbert's ε operator, but in the main part of the paper we consider the case when all choices are independent.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  16. Yuri Gurevich & Alexander Rabinovich (2000). Definability and Undefinability with Real Order at the Background. Journal of Symbolic Logic 65 (2):946-958.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  17. Andreas Blass, Yuri Gurevich & Saharon Shelah (1999). Choiceless Polynomial Time. Annals of Pure and Applied Logic 100 (1-3):141-187.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  18. Anita Feferman, Solomon Feferman, Robert Goldblatt, Yuri Gurevich, Klaus Grue, Sven Ove Hansson, Lauri Hella, Robert K. Meyer & Petri Mäenpää (1997). Stål Anderaa (Oslo), A Traktenbrot Inseparability Theorem for Groups. Peter Dybjer (G Öteborg), Normalization by Yoneda Embedding (Joint Work with D. Cubric and PJ Scott). Abbas Edalat (Imperial College), Dynamical Systems, Measures, Fractals, and Exact Real Number Arithmetic Via Domain Theory. [REVIEW] Bulletin of Symbolic Logic 3 (4).
    Direct download  
     
    My bibliography  
     
    Export citation  
  19. Thomas Eiter, Georg Gottlob & Yuri Gurevich (1996). Normal Forms for Second-Order Logic Over Finite Structures, and Classification of NP Optimization Problems. Annals of Pure and Applied Logic 78 (1-3):111-125.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  20. Yuri Gurevich & Saharon Shelah (1996). On Finite Rigid Structures. Journal of Symbolic Logic 61 (2):549-562.
    The main result of this paper is a probabilistic construction of finite rigid structures. It yields a finitely axiomatizable class of finite rigid structures where no L ω ∞,ω formula with counting quantifiers defines a linear order.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  21. 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  
  22. 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  
  23. Yuri Gurevich (1995). Preface. Annals of Pure and Applied Logic 73 (1):1.
     
    My bibliography  
     
    Export citation  
  24. Yuri Gurevich & Saharon Shelah (1989). On the Strength of the Interpretation Method. Journal of Symbolic Logic 54 (2):305-323.
    In spite of the fact that true arithmetic reduces to the monadic second-order theory of the real line, Peano arithmetic cannot be interpreted in the monadic second-order theory of the real line.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  25. Yuri Gurevich & Saharon Shelah (1989). Time Polynomial in Input or Output. Journal of Symbolic Logic 54 (3):1083-1088.
    We introduce the class PIO of functions computable in time that is polynomial in max{the length of input, the length of output}, observe that there is no notation system for total PIO functions but there are notation systems for partial PIO functions, and give an algebra of partial PIO functions from binary strings to binary strings.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  26. Yuri Gurevich & Saharon Shelah (1986). Fixed-Point Extensions of First-Order Logic. Annals of Pure and Applied Logic 32:265-280.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  27. John P. Burgess & Yuri Gurevich (1985). The Decision Problem for Linear Temporal Logic. Notre Dame Journal of Formal Logic 26 (2):115-128.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  28. Yuri Gurevich & Saharon Shelah (1985). The Decision Problem for Branching Time Logic. Journal of Symbolic Logic 50 (3):668-681.
    The theory of trees with additional unary predicates and quantification over nodes and branches embraces a rich branching time logic. This theory was reduced in the companion paper to the first-order theory of binary, bounded, well-founded trees with additional unary predicates. Here we prove the decidability of the latter theory.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  29. Warren D. Goldfarb, Yuri Gurevich & Saharon Shelah (1984). A Decidable Subclass of the Minimal Gödel Class with Identity. Journal of Symbolic Logic 49 (4):1253-1261.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  30. Yuri Gurevich & Harry R. Lewis (1984). The Word Problem for Cancellation Semigroups with Zero. Journal of Symbolic Logic 49 (1):184-191.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  31. Yuri Gurevich (1983). Decision Problem for Separated Distributive Lattices. Journal of Symbolic Logic 48 (1):193-196.
    It is well known that for all recursively enumerable sets X 1 , X 2 there are disjoint recursively enumerable sets Y 1 , Y 2 such that $Y_1 \subseteq X_1, Y_2 \subseteq X_2$ and Y 1 ∪ Y 2 = X 1 ∪ X 2 . Alistair Lachlan called distributive lattices satisfying this property separated. He proved that the first-order theory of finite separated distributive lattices is decidable. We prove here that the first-order theory of all separated distributive lattices (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  32. Yuri Gurevich, Menachem Magidor & Saharon Shelah (1983). The Monadic Theory of Ω12. Journal of Symbolic Logic 48 (2):387 - 398.
    Assume ZFC + "There is a weakly compact cardinal" is consistent. Then: (i) For every $S \subseteq \omega, \mathrm{ZFC} +$ "S and the monadic theory of ω 2 are recursive each in the other" is consistent; and (ii) ZFC + "The full second-order theory of ω 2 is interpretable in the monadic theory of ω 2 " is consistent.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  33. Yuri Gurevich, Menachem Magidor & Saharon Shelah (1983). The Monadic Theory of $Omega^1_2$. Journal of Symbolic Logic 48 (2):387-398.
    Assume ZFC + "There is a weakly compact cardinal" is consistent. Then: (i) For every $S \subseteq \omega, \mathrm{ZFC} +$ "$S$ and the monadic theory of $\omega_2$ are recursive each in the other" is consistent; and (ii) ZFC + "The full second-order theory of $\omega_2$ is interpretable in the monadic theory of $\omega_2$" is consistent.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  34. Yuri Gurevich & Saharon Shelah (1983). Interpreting Second-Order Logic in the Monadic Theory of Order. Journal of Symbolic Logic 48 (3):816-828.
    Under a weak set-theoretic assumption we interpret second-order logic in the monadic theory of order.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  35. Yuri Gurevich & Saharon Shelah (1983). Random Models and the Gödel Case of the Decision Problem. Journal of Symbolic Logic 48 (4):1120-1124.
    In a paper of 1933 Godel proved that every satisfiable first-order ∀ 2 ∃ * sentence has a finite model. Actually he constructed a finite model in an ingenious and sophisticated way. In this paper we use a simple and straightforward probabilistic argument to establish existence of a finite model of an arbitrary satisfiable ∀ 2 ∃ * sentence.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  36. Yuri Gurevich & Saharon Shelah (1983). Rabin's Uniformization Problem. Journal of Symbolic Logic 48 (4):1105-1119.
    The set of all words in the alphabet {l, r} forms the full binary tree T. If x ∈ T then xl and xr are the left and the right successors of x respectively. We consider the monadic second-order language of the full binary tree with the two successor relations. This language allows quantification over elements of T and over arbitrary subsets of T. We prove that there is no monadic second-order formula φ * (X, y) such that for every (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  37. Yuri Gurevich & Saharon Shelah (1982). Monadic Theory of Order and Topology in ZFC. Annals of Mathematical Logic 23 (2-3):179-198.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  38. Yuri Gurevich (1979). Modest Theory of Short Chains. I. Journal of Symbolic Logic 44 (4):481-490.
    This is the first part of a two part work on the monadic theory of short orders (embedding neither ω 1 nor ω 1 * ). This part provides the technical groundwork for decidability results. Other applications are possible.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  39. Yuri Gurevich & Saharon Shelah (1979). Modest Theory of Short Chains. II. Journal of Symbolic Logic 44 (4):491-502.
    We analyse here the monadic theory of the rational order, the monadic theory of the real line with quantification over "small" subsets and models of these theories. We prove that the results are in some sense the best possible.
    Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  40. Yuri Gurevich (1977). Expanded Theory of Ordered Abelian Groups. Annals of Mathematical Logic 12 (2):193-228.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  41. Yuri Gurevich (1977). Intuitionistic Logic with Strong Negation. Studia Logica 36 (1-2):49 - 59.
    This paper is a reaction to the following remark by grzegorczyk: "the compound sentences are not a product of experiment. they arise from reasoning. this concerns also negations; we see that the lemon is yellow, we do not see that it is not blue." generally, in science the truth is ascertained as indirectly as falsehood. an example: a litmus-paper is used to verify the sentence "the solution is acid." this approach gives rise to a (very intuitionistic indeed) conservative extension of (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  42. Yuri Gurevich (1976). The Decision Problem for Standard Classes. Journal of Symbolic Logic 41 (2):460-464.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation