9 found
Order:
  1.  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   6 citations  
  2.  35
    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.  27
    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  
  4. 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  
  5.  12
    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.
  6.  18
    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  
  7.  27
    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  
  8.  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  
  9.  12
    Review: Eitan Gurari, An Introduction to the Theory of Computation. [REVIEW]William I. Gasarch - 1991 - Journal of Symbolic Logic 56 (1):338-339.