12 found
Sort by:
  1. P. P. Prabhudesai, Sanjay Jain, Aziz Keshvani & K. P. Kulkarni (forthcoming). Research Analysis Report. Ethics.
    Direct download  
     
    My bibliography  
     
    Export citation  
  2. Alexander Gavruskin, Sanjay Jain, Bakhadyr Khoussainov & Frank Stephan (2014). Graphs Realised by R.E. Equivalence Relations. Annals of Pure and Applied Logic 165 (7-8):1263-1290.
    We investigate dependence of recursively enumerable graphs on the equality relation given by a specific r.e. equivalence relation on ω. In particular we compare r.e. equivalence relations in terms of graphs they permit to represent. This defines partially ordered sets that depend on classes of graphs under consideration. We investigate some algebraic properties of these partially ordered sets. For instance, we show that some of these partial ordered sets possess atoms, minimal and maximal elements. We also fully describe the isomorphism (...)
    Direct download  
     
    My bibliography  
     
    Export citation  
  3. John Case & Sanjay Jain (2011). Rice and Rice-Shapiro Theorems for Transfinite Correction Grammars. Mathematical Logic Quarterly 57 (5):504-516.
    Hay and, then, Johnson extended the classic Rice and Rice-Shapiro Theorems for computably enumerable sets, to analogs for all the higher levels in the finite Ershov Hierarchy. The present paper extends their work to analogs in the transfinite Ershov Hierarchy. Some of the transfinite cases are done for all transfinite notations in Kleene's important system of notations, equation image. Other cases are done for all transfinite notations in a very natural, proper subsystem equation image of equation image, where equation image (...)
    No categories
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  4. Lorenzo Carlucci, John Case & Sanjay Jain (2009). Learning Correction Grammars. Journal of Symbolic Logic 74 (2):489-516.
    We investigate a new paradigm in the context of learning in the limit, namely, learning correction grammars for classes of computably enumerable (c.e.) languages. Knowing a language may feature a representation of it in terms of two grammars. The second grammar is used to make corrections to the first grammar. Such a pair of grammars can be seen as a single description of (or grammar for) the language. We call such grammars correction grammars. Correction grammars capture the observable fact that (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  5. John Case, Keh-Jiann Chen, Sanjay Jain, Wolfgang Merkle & James S. Royer (2006). Generality's Price: Inescapable Deficiencies in Machine-Learned Programs. Annals of Pure and Applied Logic 139 (1):303-326.
    This paper investigates some delicate tradeoffs between the generality of an algorithmic learning device and the quality of the programs it learns successfully. There are results to the effect that, thanks to small increases in generality of a learning device, the computational complexity of some successfully learned programs is provably unalterably suboptimal. There are also results in which the complexity of successfully learned programs is asymptotically optimal and the learning device is general, but, still thanks to the generality, some of (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  6. Andris Ambainis, John Case, Sanjay Jain & Mandayam Suraj (2004). Parsimony Hierarchies for Inductive Inference. Journal of Symbolic Logic 69 (1):287-327.
    Freivalds defined an acceptable programming system independent criterion for learning programs for functions in which the final programs were required to be both correct and "nearly" minimal size, i.e., within a computable function of being purely minimal size. Kinber showed that this parsimony requirement on final programs limits learning power. However, in scientific inference, parsimony is considered highly desirable. A lim-computablefunction is (by definition) one calculable by a total procedure allowed to change its mind finitely many times about its output. (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  7. Sanjay Jain & Jochen Nessel (2001). Some Independence Results for Control Structures in Complete Numberings. Journal of Symbolic Logic 66 (1):357-382.
    Acceptable programming systems have many nice properties like s-m-n-Theorem, Composition and Kleene Recursion Theorem. Those properties are sometimes called control structures, to emphasize that they yield tools to implement programs in programming systems. It has been studied, among others by Riccardi and Royer, how these control structures influence or even characterize the notion of acceptable programming system. The following is an investigation, how these control structures behave in the more general setting of complete numberings as defined by Mal'cev and Eršov.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  8. Vivek S. Borkar, Sanjay Jain & Govindan Rangarajan (1998). Dynamics of Individual Specialization and Global Diversification in Communities. Complexity 3 (3):50-56.
    No categories
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  9. Sanjay Jain & Arun Sharma (1997). Characterizing Language Identification in Terms of Computable Numberings. Annals of Pure and Applied Logic 84 (1):51-72.
    Identification of programs for computable functions from their graphs and identification of grammars for recursively enumerable languages from positive data are two extensively studied problems in the recursion theoretic framework of inductive inference.In the context of function identification, Freivalds et al. have shown that only those collections of functions, , are identifiable in the limit for which there exists a 1-1 computable numbering ψ and a discrimination function d such that1. for each , the number of indices i such that (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  10. Sanjay Jain & Arun Sharma (1997). The Structure of Intrinsic Complexity of Learning. Journal of Symbolic Logic 62 (4):1187-1201.
    Limiting identification of r.e. indexes for r.e. languages (from a presentation of elements of the language) and limiting identification of programs for computable functions (from a graph of the function) have served as models for investigating the boundaries of learnability. Recently, a new approach to the study of "intrinsic" complexity of identification in the limit has been proposed. This approach, instead of dealing with the resource requirements of the learning algorithm, uses the notion of reducibility from recursion theory to compare (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  11. Ganesh Baliga, John Case, Sanjay Jain & Mandayam Suraj (1994). Machine Learning of Higher-Order Programs. Journal of Symbolic Logic 59 (2):486-500.
    A generator program for a computable function (by definition) generates an infinite sequence of programs all but finitely many of which compute that function. Machine learning of generator programs for computable functions is studied. To motivate these studies partially, it is shown that, in some cases, interesting global properties for computable functions can be proved from suitable generator programs which cannot be proved from any ordinary programs for them. The power (for variants of various learning criteria from the literature) of (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  12. Lance Fortnow, William Gasarch, Sanjay Jain, Efim Kinber, Martin Kummer, Stuart Kurtz, Mark Pleszkovich, Theodore Slaman, Robert Solovay & Frank Stephan (1994). Extremes in the Degrees of Inferability. 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 (3 more)  
     
    My bibliography  
     
    Export citation