19 found
Order:
Disambiguations
William Gasarch [11]William I. Gasarch [9]
  1. Learning Via Queries in $\Lbrack +,.William I. Gasarch, Mark G. Pleszkoch & Robert Solovay - 1992 - Journal of Symbolic Logic 57 (1):53-81.
    We prove that the set of all recursive functions cannot be inferred using first-order queries in the query language containing extra symbols $\lbrack +, . The proof of this theorem involves a new decidability result about Presburger arithmetic which is of independent interest. Using our machinery, we show that the set of all primitive recursive functions cannot be inferred with a bounded number of mind changes, again using queries in $\lbrack +, . Additionally, we resolve an open question in [7] (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  2.  30
    Bounded Query Classes and the Difference Hierarchy.Richard Beigel, William I. Gasarch & Louise Hay - 1989 - Archive for Mathematical Logic 29 (2):69-84.
    LetA be any nonrecursive set. We define a hierarchy of sets (and a corresponding hierarchy of degrees) that are reducible toA based on bounding the number of queries toA that an oracle machine can make. WhenA is the halting problemK our hierarchy of sets interleaves with the difference hierarchy on the r.e. sets in a logarithmic way; this follows from a tradeoff between the number of parallel queries and the number of serial queries needed to compute a function with oracleK.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  3.  24
    Reverse Mathematics and Recursive Graph Theory.William Gasarch & Jeffry L. Hirst - 1998 - Mathematical Logic Quarterly 44 (4):465-473.
    We examine a number of results of infinite combinatorics using the techniques of reverse mathematics. Our results are inspired by similar results in recursive combinatorics. Theorems included concern colorings of graphs and bounded graphs, Euler paths, and Hamilton paths.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  4.  24
    Learning Via Queries in [ +, < ].William I. Gasarch, Mark G. Pleszkoch & Robert Solovay - 1992 - Journal of Symbolic Logic 57 (1):53-81.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  5.  17
    Extremes in the Degrees of Inferability.Lance Fortnow, William Gasarch, Sanjay Jain, Efim Kinber, Martin Kummer, Stuart Kurtz, Mark Pleszkovich, Theodore Slaman, Robert Solovay & Frank Stephan - 1994 - Annals of Pure and Applied Logic 66 (3):231-276.
    Most theories of learning consider inferring a function f from either observations about f or, questions about f. We consider a scenario whereby the learner observes f and asks queries to some set A. If I is a notion of learning then I[A] is the set of concept classes I-learnable by an inductive inference machine with oracle A. A and B are I-equivalent if I[A] = I[B]. The equivalence classes induced are the degrees of inferability. We prove several results about (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  6.  9
    On the Complexity of Finding the Chromatic Number of a Recursive Graph I: The Bounded Case.Richard Beigel & William I. Gasarch - 1989 - Annals of Pure and Applied Logic 45 (1):1-38.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  7.  12
    The Complexity of ODDnA.Richard Beigel, William Gasarch, Martin Kummer, Georgia Martin, Timothy Mcnicholl & Frank Stephan - 2000 - Journal of Symbolic Logic 65 (1):1-18.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  8.  10
    On the Complexity of Finding the Chromatic Number of a Recursive Graph II: The Unbounded Case.Richard Beigel & William I. Gasarch - 1989 - Annals of Pure and Applied Logic 45 (3):227-246.
  9.  9
    Nondeterministic Bounded Query Reducibilities.Richard Beigel, William Gasarch & Jim Owings - 1989 - Annals of Pure and Applied Logic 41 (2):107-118.
  10.  16
    Learning Via Queries in $\Lbrack +, < \Rbrack$.William I. Gasarch, Mark G. Pleszkoch & Robert Solovay - 1992 - Journal of Symbolic Logic 57 (1):53 - 81.
    We prove that the set of all recursive functions cannot be inferred using first-order queries in the query language containing extra symbols $\lbrack +, < \rbrack$. The proof of this theorem involves a new decidability result about Presburger arithmetic which is of independent interest. Using our machinery, we show that the set of all primitive recursive functions cannot be inferred with a bounded number of mind changes, again using queries in $\lbrack +, < \rbrack$. Additionally, we resolve an open question (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  11.  25
    On the Finiteness of the Recursive Chromatic Number.William I. Gasarch & Andrew C. Y. Lee - 1998 - Annals of Pure and Applied Logic 93 (1-3):73-81.
    A recursive graph is a graph whose vertex and edge sets are recursive. A highly recursive graph is a recursive graph that also has the following property: one can recursively determine the neighbors of a vertex. Both of these have been studied in the literature. We consider an intermediary notion: Let A be a set. An A-recursive graph is a recursive graph that also has the following property: one can recursively-in-A determine the neighbors of a vertex. We show that, if (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  12.  51
    The Complexity of Oddan.Richard Beigel, William Gasarch, Martin Kummer, Georgia Martin, Timothy McNicholl & Frank Stephan - 2000 - Journal of Symbolic Logic 65 (1):1 - 18.
    For a fixed set A, the number of queries to A needed in order to decide a set S is a measure of S's complexity. We consider the complexity of certain sets defined in terms of A: $ODD^A_n = \{(x_1, \dots ,x_n): {\tt\#}^A_n(x_1, \dots, x_n) \text{is odd}\}$ and, for m ≥ 2, $\text{MOD}m^A_n = \{(x_1, \dots ,x_n):{\tt\#}^A_n(x_1, \dots ,x_n) \not\equiv 0 (\text{mod} m)\},$ where ${\tt\#}^A_n(x_1, \dots ,x_n) = A(x_1)+\cdots+A(x_n)$ . (We identify A(x) with χ A (x), where χ A is (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  13.  9
    Distinct Volume Subsets Via Indiscernibles.William Gasarch & Douglas Ulrich - 2019 - Archive for Mathematical Logic 58 (3-4):469-483.
    Erdős proved that for every infinite \ there is \ with \, such that all pairs of points from Y have distinct distances, and he gave partial results for general a-ary volume. In this paper, we search for the strongest possible canonization results for a-ary volume, making use of general model-theoretic machinery. The main difficulty is for singular cardinals; to handle this case we prove the following. Suppose T is a stable theory, \ is a finite set of formulas of (...)
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  14.  16
    Gurari Eitan. An Introduction to the Theory of Computation. Principles of Computer Science Series. Computer Science Press, Rockville, Md., 1989, Xii + 314 Pp. [REVIEW]William I. Gasarch - 1991 - Journal of Symbolic Logic 56 (1):338-339.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  15.  22
    The Structure of the Honest Polynomial M-Degrees.Rod Downey, William Gasarch & Michael Moses - 1994 - Annals of Pure and Applied Logic 70 (2):113-139.
    We prove a number of structural theorems about the honest polynomial m-degrees contingent on the assumption P = NP . In particular, we show that if P = NP , then the topped finite initial segments of Hm are exactly the topped finite distributive lattices, the topped initial segments of Hm are exactly the direct limits of ascending sequences of finite distributive lattices, and all recursively presentable distributive lattices are initial segments of Hm ∩ RE. Additionally, assuming ¦∑¦ = 1, (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  16.  12
    Review: Eitan Gurari, An Introduction to the Theory of Computation. [REVIEW]William I. Gasarch - 1991 - Journal of Symbolic Logic 56 (1):338-339.
  17.  11
    The Complexity of Learning SUBSEQ(A).Stephen Fenner, William Gasarch & Brian Postow - 2009 - Journal of Symbolic Logic 74 (3):939-975.
    Higman essentially showed that if A is any language then SUBSEQ(A) is regular, where SUBSEQ(A) is the language of all subsequences of strings in A. Let s1, s2, s3, . . . be the standard lexicographic enumeration of all strings over some finite alphabet. We consider the following inductive inference problem: given A(s1), A(s2), A(s3), . . . . learn, in the limit, a DFA for SUBSEQU). We consider this model of learning and the variants of it that are usually (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  18.  11
    Max and Min Limiters.James Owings, William Gasarch & Georgia Martin - 2002 - Archive for Mathematical Logic 41 (5):483-495.
    If and the function is partial recursive, it is easily seen that A is recursive. In this paper, we weaken this hypothesis in various ways (and similarly for ``min'' in place of ``max'') and investigate what effect this has on the complexity of A. We discover a sharp contrast between retraceable and co-retraceable sets, and we characterize sets which are the union of a recursive set and a co-r.e., retraceable set. Most of our proofs are noneffective. Several open questions are (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  19.  4
    Automata Techniques for Query Inference Machines.William Gasarch & Geoffrey R. Hird - 2002 - Annals of Pure and Applied Logic 117 (1-3):169-201.
    In prior papers the following question was considered: which classes of computable sets can be learned if queries about those sets can be asked by the learner? The answer depended on the query language chosen. In this paper we develop a framework for studying this question. Essentially, once we have a result for queries to [S,<]2, we can obtain the same result for many different languages. We obtain easier proofs of old results and several new results. An earlier result we (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark