Research Publications
Book
Jain, S., Osherson, D., Royer, J., and Sharma, A. (1999), Systems That Learn: An Introduction to Learning Theory, second edition, The MIT Press, Cambridge, MA.
Books (edited)
Arimura, A., Jain, S., and Sharma, A. (Editors), (2000), Algorithmic Learning Theory, Lecture Notes in Artificial Intelligence, No. 1968, Springer-Verlag.
Du, D.-Z., Eades, P., Estivill-Castro, V., Lin, X., and Sharma, A. (Editors), (2000), Computing and Combinatorics, Lecture Notes in Computer Science, No. 1858, Springer-Verlag.
Arikawa, A. and Sharma, A. (Editors), (1996), Algorithmic Learning Theory, Lecture Notes in Artificial Intelligence, No. 1160, Springer-Verlag.
Book Chapters
Martin, E., Sharma, A., and Stephan, F. (2007) “Deduction, Induction and Beyond in Parametric Logic.” In Friend, M., Goethe, N., and Harizanov, V., (eds.) Induction, Algorithmic Learning Theory, and Philosophy, Series Logic, Epistemology, and the Unity of Science, Vol. 9, pp. 55 – 110. Dordrecht, Springer.
Jain, S. and Sharma, A. (1995) “On Identification by Teams and Probabilistic Machines.” In Klaus P. Jantke and Steffen Lange (eds.), Algorithmic Learning for Knowledge-Based Systems, Lecture Notes in Artificial Intelligence, Volume 961, pp. 109-146, Springer-Verlag, 1995.
Refereed journal articles
Martin, E., Sharma, A., and Stephan, F. (2007) “On the Data Consumption Benefits of Accepting Increased Uncertainty.” In Theoretical Computer Science, Vol 382(3) pp. 170 – 182, Elsevier.
Martin E., Sharma A. and Stephan F. (2006) “Unifying Logic, Topology and Learning in Parametric Logic.” In Theoretical Computer Science, Vol. 350(1), pp. 102 – 124, Elsevier.
Case, J., Jain, S., Martin, E., and Sharma, A. (2006) “Identifying Clusters from Positive Data.” In SIAM Journal on Computing, Vol. 36(1), pp. 28 – 55.
Martin, E., Sharma, A., and Stephan, F. (2006) “On the Ordinal VC—Dimension and Some Notions of Complexity.” In Theoretical Computer Science, Vol. 364(1), pp. 62—76, Elsevier.
Sharma, A., Stephan, F., and Ventsov, Y. (2004) “Generalised Notions of Mind Change Complexity.” In Information and Computation, Vol. 189, pp. 235 – 262, Academic Press.
Case, J., Kinber, E., Sharma, A., and Stephan, A. (2004) “On the classification of computable languages.” In Information and Computation, Vol. 192, pp. 15 – 40, Academic Press.
Martin, E., Sharma, A., and Stephan, F. (2003) “Learning power and language expressiveness.” In Theoretical Computer Science. 298(2) pp. 365 – 383.
Ignjatovic, A. and Sharma, A. (2004) “Some applications of logic to feasibility in higher types.” In ACM Transactions on Computational Logic. Vol. 5(2), pp. 332 – 350.
Jain, S. and Sharma, A. (2001) "On a Generalised Notion of Mistake Bounds." In Information and Computation, Vol. 166, pp. 156-166, Academic Press.
Case, J., Ott, M., Sharma, A., and Stephan, F. (2002) “Learning to Win Process-Control Games Watching Game-Masters.” In Information and Computation, Vol. 174, pp. 1-19, Academic Press.
Jain, S. and Sharma, A. (2002) “Mind Change Complexity of Learning Logic Programs.” In Theoretical Computer Science, Vol. 284, pp. 143-160, Elsevier (special issue of selected papers invited for review from EuroCOLT'99)
Case, J., Jain, S., Kaufmann, S., Sharma, A., and Stephan, F. (2001) “Predictive Learning Models for Concept Drift.'' In Theoretical Computer Science, Vol. 268, pp. 323-349, Elsevier. (Special issue of selected papers invited for review from the Ninth International Conference on Algorithmic Learning Theory)
Case, J., Jain, S., and Sharma, A. (2001) “Synthesizing Noise-Tolerant Language Learners.” In Theoretical Computer Science, Vol. 261, No. 1, pp. 31 - 56, Elsevier. (Special issue of selected papers invited for review from the Eighth International Conference on Algorithmic Learning Theory)
Case, J., Jain, S., Ott, M., Sharma, A., and Stephan, F. (2000) “Robust Learning Aided by Context.” In Journal of Computer and System Sciences, Vol. 60, No. 2, pp. 234 - 257, Academic Press. (Special issue of selected papers invited for review from the 1998 Annual Conference on Computational Learning Theory)
Jain, S. and Sharma, A. (2000) “Team Learning of Computable Languages.” In Theory of Computing Systems, Vol. 33, No. 1, pp. 35-58, Springer-Verlag.
Ambainis, A., Jain, S., and Sharma, A. (1999) “Ordinal Mind Change Complexity of Language Identification.” In Theoretical Computer Science, Vol. 220, No. 2, pp. 323-343, Elsevier.
Sharma, A. (1998) “A note on batch and incremental learnability.” In Journal of Computer and System Sciences, Vol. 56, pp. 272 - 276, Academic Press.
Jain, S. and Sharma, A. (1998) "Generalisation and Specialisation Strategies for Identifying Languages." In Annals of Mathematics and Artificial Intelligence, Vol. 23, pp. 1-23 Elsevier. (Special issue of selected papers invited for review from the Fifth International Workshop on Algorithmic Learning Theory, Reinhardsbrunn, Germany)
Jain, S. and Sharma A. (1997) “The Structure of Intrinsic Complexity of Learning.” In Journal of Symbolic Logic, Vol. 62, No. 4, pp. 1187 - 1201, Association for Symbolic Logic, Inc.
Baliga, G., Jain, S., and Sharma, A. (1997) “Learning from Multiple Sources of Inaccurate Data.” In SIAM Journal of Computing, Vol. 26, No. 4, 961 - 990.
Jain, S. and Sharma, A. (1997) "Characterising language identification in terms of computable numberings." In Annals of Pure and Applied Logic, Vol. 84, pp. 51 - 72, Elsevier. (Special issue of selected papers invited for review from the Fifth Asian Logic Conference, Singapore)
Jain, S. and Sharma, A. (1997) “Elementary Formal Systems, Intrinsic Complexity, and Procrastination.” In Information and Computation, Vol. 132, No. 1, pp. 65 - 84, Academic Press.
Jain, S. and Sharma, A. (1996) “Computational Limits on Team Identification of Languages.” In Information and Computation, Vol. 130, No. 1, pp. 19 - 60, Academic Press.
Case, J., Jain, S., and Sharma, A. (1996) “Machine Induction without Revolutionary Changes in Hypothesis Size.” In Information and Computation, Vol. 128, No. 2, pp. 73 - 86, Academic Press.
Case, J., Jain, S., and Sharma, A. (1996) “Anomalous Learning Helps Succinctness.” In Theoretical Computer Science, Vol. 164, Nos. 1--2, pp. 13--28, Elsevier.
Jain, S. and Sharma, A. (1996) “The Intrinsic Complexity of Language Identification.” In Journal of Computer and System Science, Vol. 52, No. 3, 393--402, Academic Press. (Special issue of selected papers invited for review from the Seventh Annual Conference on Computational Learning Theory, New Brunswick, USA.)
Jain, S., Sharma, A., and Velauthapillai, M. (1996) “Finite Identification of Functions by Teams with Success Ratio ½ and Above.” In Information and Computation, Vol. 121, No. 2, pp. 201 - 213, Academic Press.
Jain, S. and Sharma, A. (1995) “On Aggregating Teams of Learning Machines.” In Theoretical Computer Science, Vol. 137, pp. 85 - 108, Elsevier. (Special issue of selected papers invited for review from the Fourth International Workshop on Algorithmic Learning Theory, Tokyo, Japan.)
Jain, S. and Sharma, A. (1995) “Prudence in Vacillatory Identification of Languages.” In Mathematical Systems Theory, Vol. 28, No. 3, pp. 267 - 279, Springer-Verlag. (Journal renamed Theory of Computing Systems)
Case, J., Jain, S., and Sharma, A. (1995) “Complexity Issues for Vacillatory Function Identification.” In Information and Computation, Vol. 116, No. 2, pp. 174 - 192, Academic Press.
Case, J., Jain, S., and Sharma, A. (1994) “Vacillatory Learning of Nearly Minimal Size Grammars.” In Journal of Computer and System Sciences, Vol. 49, No. 2, pp. 189 - 207, Academic Press.
Jain, S. and Sharma, A. (1994) "Characterising Language Identification by Standardizing Operations." In Journal of Computer and System Sciences, Vol. 49, No. 1, pp. 96 - 107, Academic Press.
Jain, S. and Sharma, A. (1994) “Program Size Restrictions in Computational Learning.” In Theoretical Computer Science, Vol. 127, No. 2, 351 - 386, Elsevier.
Jain, S. and Sharma, A. (1993) “On the Nonexistence of Maximal Inference Degrees for Language Identification.” In Information Processing Letters, Vol. 47, No. 2, pp. 81 - 88, Elsevier.
Jain, S. and Sharma, A. (1993) “Learning with the Knowledge of an Upper Bound on Program Size.” In Information and Computation, Vol. 102, No. 1, pp. 118 - 166, Academic Press.
Case, J., Jain, S., Sharma, A. (1992) “On Learning Limiting Programs.” In International Journal of Foundations of Computer Science, Vol. 3, No. 1, pp. 93 - 115, World Scientific Publishers.
Jain, S., and Sharma, A. (1991) “Learning in the Presence of Partial Explanations.” In Information and Computation, Vol. 95, No. 2, pp. 162 - 191, Academic Press.
Articles in refereed published proceedings
Martin, E. and Sharma, A. (2005) “On a Syntactic Characterisation of Classification with a Mind Change Bound” in Auer, P. and Meir, R. (ed.) Proceedings of the 18th Annual Conference on Learning Theory, Lecture Notes in Artificial Intelligence 3559, pp. 413 – 428, Springer.
Sharma, A. (2004) “Web Searching and Sigma2 Queries” in Xu, J., Lin, X., Lu, H., and Zhang, Y., Advanced Web Technologies and Applications, Proceedings of the 6th Asia-Pacific Web Conference, Hangzhou, China, Lecture Notes in Computer Science 3007, pp. 20 – 23, Springer.
Martin E., Sharma, A., and Stephan, F. (2004) “On the Data Consumption Benefits of Accepting Increased Uncertainty” in Ben-David, S., Case, J., and Maruoka, A. (eds.) Proceedings of the 15th International Conference on Algorithmic Learning Theory, Padova, Italy, Lecture Notes in Computer Science, Vol. 3244, pp. 83 – 98, Springer.
Case, J., Jain, S., Martin, E., and Sharma, A. (2004) “Identifying Clusters from Positive Data” in Paliouras, G. and Sakakibara, Y. (eds.) Grammatical Inference: Algorithms and Applications, 7th International Colloquium, Athens, Greece, Lecture Notes in Computer Science 3264, pp. 103 – 114, Springer.
Martin, E., Sharma, A. and Stephan, F. (2003) “On Ordinal VC-Dimension and Some Notions of Complexity” in Gavalda, R. Jantke, K. and Takimoto, E. (ed.) Proceedings of the 14th International Conference on Algorithmic Learning Theory, Lecture Notes in Artificial Intelligence 2842, Springer-Verlag.
Martin, E., Sharma, A., and Stephan, F. (2002) “Learning, Logic and Topology in a Common Framework” in Cesa-Bianchi, N., Numao, M. and Reischuk, R. (ed.) Proceedings of the 13th International Conference on Algorithmic Learning Theory, Lecture Notes in Artificial Intelligence 2533, Springer-Verlag.
Martin, E., Nguyen, P. Sharma, A. Stephan, F. (2002) “Learning in Logic with RichProlog” in Stuckey, P. (ed.) Proceedings of the 18th International Conference on Logic Programming, Lecture Notes in Computer Science 2401, Springer-Verlag.
Martin, E., Sharma, A. and Stephan, F. (2001) “A General Theory of Deduction, Induction, and Learning” in Jantke, K. and Shinohara, A. (ed.) Proceedings of the 4th International Conference on Discovery Science, Lecture Notes in Artificial Intelligence 2226, Springer-Verlag.
Mitchell, A., Scheffer, T., Sharma, A., and Stephan, F. (1999) “The VC-Dimension of Subclasses of Pattern Languages” in O. Watanabe and T. Yokomori (editors), Proceedings of the Tenth International Conference on Algorithmic Learning Theory (ALT'99), Tokyo, Lecture Notes in Artificial Intelligence, Vol. 1720, pp. 93 - 105, Springer-Verlag, December 1999.
Martin, E. and Sharma, A. (1999) “On Sufficient Conditions for Learnability of Logic Programs from Positive Data” in Saso Dzeroski and Peter Flach (editors), Proceedings of the Ninth International Conference on Inductive Logic Programming (ILP'99), Bled, Slovenia, Lecture Notes in Artificial Intelligence, Vol.1634, pp. 198 - 209, Springer-Verlag, June 1999.
Jain, S. and Sharma, A. (1999) "On a Generalised Notion of Mistake Bounds" in Proceedings of the Twelfth Annual Conference on Computational Learning Theory (COLT'99), Santa Cruz, 249--256, ACM Press, July 1999.
Jain, S. and Sharma, A. (1999) “Mind Change Complexity of Learning Logic Programs” in P. Fischer and H.U. Simon (editors) Proceedings of the 4th European Conference on Computational Learning Theory (EuroCOLT'99), Nordkirchen Castle, Germany, Lecture Notes in Artificial Intelligence, Vol. 1572, pp. 198--213, Springer-Verlag, March 1999.
McCreath, E. and Sharma, A. (1998) “ LIME: A System for Learning Relations” in M. Richter et al. (editors), Proceedings of the 9th International Conference on Algorithmic Learning Theory (ALT'98), Otzenhausen, Germany, Lecture Notes in Artificial Intelligence, Vol. 1501, pp. 336 - 374, Springer-Verlag, October 1998.
Case, J., Ott, M., Sharma, A., and Stephan, F. (1998) “Learning to Win Process-Control Games Watching Game-Masters” in M. Richter et al. (editors) Proceedings of the 9th International Conference on Algorithmic Learning Theory (ALT'98), Otzenhausen, Germany, Lecture Notes in Artificial Intelligence, Vol. 1501, pp. 31 - 45, Springer-Verlag, October 1998.
Case, J., Jain, S., Kaufmann, S., Sharma, A., and Stephan, F. (1998) “Predictive Learning Models for Concept Drift” in M. Richter et al. (editors), Proceedings of the 9th International Conference on Algorithmic Learning Theory (ALT'98) Otzenhausen, Germany, Lecture Notes in Artificial Intelligence, Vol. 1501, pp. 276 - 290, Springer-Verlag, October 1998.
Case, J., Jain, S., Ott, M., Sharma, A., and Stephan, F. (1998) “Robustly Learning Aided by Context” in the Proceedings of the Eleventh Annual Conference on Computational Learning Theory, (COLT'98), Wisconsin-Madison, pp. 44 - 55, ACM Press, July 1998.
Case, J., Jain, S., and Sharma, A. (1997) “Synthesizing Noise-Tolerant Language Learners” in M. Li and A. Maruoka (editors), Proceedings of the 8th International Workshop on Algorithmic Learning Theory (ALT'97), Sendai, Japan, Lecture Notes in Artificial Intelligence, Vol. 1316, pp. 228 - 243, Springer-Verlag, October 1997.
McCreath, E. and Sharma, A. (1997) “ILP with Noise and Fixed Example Size -A Bayesian Approach” in the Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, (IJCAI'97), Nagoya, pp. 1310 - 1315, distributed by Morgan Kaufmann Publishers, August 1997.
Sharma, A., Stephan, F., and Ventsov, Y. (1997) "Generalised Notions of Mind Change Complexity" in the Proceedings of the Tenth Annual Conference on Computational Learning Theory, (COLT'97), Nashville, pp. 96 - 108, ACM Press, July 1997.
Ambainis, A., Jain, S., and Sharma, A. (1997) “Ordinal Mind Change Complexity of Language Identification” in Shai Ben-David (editor), Proceedings of the Third European Conference on Computational Learning Theory, (EuroCOLT'97), Jerusalem, Israel, Lecture Notes in Artificial Intelligence, Vol. 1208, pp. 301 - 315, March 1997.
Case, J., Kinber, E., Sharma, A., and Stephan, F. (1997) “On the Classification of Computable Languages” in Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science, (STACS'97), Lubeck, Germany, Lecture Notes in Computer Science, Vol. 1200, pp. 225 - 236, Springer-Verlag, February/March 1997.
Jain, S. and Sharma, A. (1996) “Team Learning of Recursive Languages” in N. Foo and R.G. Goebel (editors), Proceedings of the Pacific Rim International Conference on Artificial Intelligence 1996, (PRICAI'96), Cairns, Lecture Notes in Artificial Intelligence, Vol.1114, pp. 324 - 335, Springer Verlag, August 1996.
Jain, S. and Sharma, A. (1996) “Elementary Formal Systems, Intrinsic Complexity, and Procrastination” in Proceedings of the Ninth Annual ACM Conference on Computational Learning Theory, (COLT'96), Italy, pp. 181 - 192, ACM Press, June 1996.
McCreath, E. and Sharma, A. (1995) “Extraction of Meta-Knowledge to Restrict the Hypothesis Space for ILP Systems” in X. Yao (editor), Proceedings of the Eighth Australian Joint Conference on Artificial Intelligence, (AI'95), Canberra, pp. 75 - 82, World Scientific, November 1995.
Case, J., Jain, S., and Sharma, A. (1995) “Machine Induction Without Revolutionary Paradigm Shifts” in K. P. Jantke, T. Shinohara, and T. Zeugmann (editors), Proceedings of the Sixth International Workshop on Algorithmic Learning Theory, (ALT'95), Fukuoka, Japan, Lecture Notes in Artificial Intelligence, Vol. 997, pp. 153 - 168, Springer-Verlag, October 1995.
Jain, S. and Sharma, A. (1995) ‘The Structure of Intrinsic Complexity of Learning” in Paul Vitanyi (editor), Computational Learning Theory, Second European Conference, (EuroCOLT'95), Barcelona, Spain, Lecture Notes in Artificial Intelligence, Vol. 904, pp. 168 - 181, Springer-Verlag, March 1995.
Jain, S. and Sharma, A. (1994) “Monotonic Strategies for Identifying recursively enumerable Languages” in Proceedings of the Fifth International Workshop on Algorithmic Learning Theory, (ALT'94), Reinhardsbrunn Castle, Germany, Lecture Notes in Artificial Intelligence, Vol. 872, pp 349 - 364, Springer-Verlag, October 1994.
Jain, S. and Sharma, A. (1994) “On the Intrinsic Complexity of Language Identification” in Proceedings of the Seventh ACM Conference on Computational Learning Theory, (COLT'94), Rutgers University, pp. 278 - 286, ACM Press, July 1994.
Jain, S. and Sharma, A. (1993) ‘On Aggregating Teams of Learning Machines” in Proceedings of the Fourth Workshop on Algorithmic Learning Theory, (ALT'93), Tokyo, Lecture Notes in Artificial Intelligence, Vol. 744, pp. 150 - 163, Springer-Verlag, November 1993.
Jain, S. and Sharma, A. (1993) “Probability is More Powerful Than Team for Identification of Languages from Positive Data” in Proceedings of the 1993 Conference on Computational Learning Theory, (COLT'93), Santa Cruz, pp. 192 - 198, ACM Press, July 1993.
Baliga, G., Jain, S., and Sharma, A. (1992) “Learning from Multiple Sources of Inaccurate Data” in Proceedings of the Third International Workshop on Analogical and Inductive Inference, (AII'92), Dagstuhl Castle, Germany, pp. 108 - 128, Lectures Notes in Artificial Intelligence, Vol. 642, Springer-Verlag, October 1992.
Jain, S. and Sharma, A. (1992) “Prudence in Vacillatory Language Identification” in Proceedings of the 1992 Algorithmic Learning Theory Workshop, (ALT'92), Tokyo, pp. 159 - 168, JSAI Press, October 1992. (Proceedings republished as Lecture Notes in Artificial Intelligence, Springer-Verlag.
Case, J., Jain, S., and Sharma, A. (1992) “On Learning Limiting Programs” in
Proceedings of the 1992 ACM Workshop on Computational Learning Theory, (COLT'92), July pp. 27 - 29, Pittsburgh, Pennsylvania, pp. 193 - 202, ACM Press, July 1992.
Case, J., Jain, S., and Sharma, A. (1991) “Complexity Issues for Vacillatory Function Identification” in S. Biswas and K. V. Nori (editors), Proceedings of the Foundations of Software Technology and Theoretical Computer Science, Eleventh Conference, New Delhi, India, Lecture Notes in Computer Science, Vol. 560, pp. 121 - 40, Springer-Verlag, December 1991.
Case, J., Jain, S., and Sharma, A. (1990) “Anomalous Learning Helps Succinctness” in S. Arikawa, et al. (editors), Proceedings of the First International Workshop on Algorithmic Learning Theory, (ALT'90), Tokyo, Japan, pp. 282 - 288, Ohmsa Publishers, October 1990. (Proceedings republished by Ohmsa-Springer.)
Jain, S. and Sharma, A. (1990) “Language Learning by a Team” in M. Paterson (editor), Proceedings of the International Colloquium on Automata, Languages, and Programming 1990, (ICALP'90), pp. 153 - 166, Springer-Verlag, July 1990.
Jain, S. and Sharma, A. (1990) “Finite Learning by a Team” in M. Fulk and J. Case (editors), Proceedings of the 1990 ACM Workshop on Computational Learning Theory, (COLT'90), pp. 163 - 177, Morgan Kaufmann Publishers, July 1990.
Jain, S. and Sharma, A. (1990) “Hypothesis Formation and Language Acquisition with Infinitely Often Correct Teacher” in R. Parikh (editor), Proceedings of the Third Conference on Theoretical Aspects of Reasoning about Knowledge, (TARK III), pp. 225 - 239, Morgan Kaufmann Publishers, March 1990.
Jain, S.and Sharma, A. (1990) "Characterising Language Learning by Standardizing Operations" in S.G. Akl, F. Fiala, and W.W. Koczkodaj (editors), Advances in Computing and Information, Proceedings of the International Conference on Computing and Information, (ICCI'90), pp. 144 - 148, Canadian Scholars' Press, Toronto, 1990.
Case, J., Jain, S., and Sharma, A. (1989) “Convergence to Nearly Minimal Size Grammars by Vacillating Learning Machines” in R. Rivest, et al. (editors), Proceedings of the 1989 Workshop on Computational Learning Theory (COLT'89), pp. 189 - 199, Morgan Kaufmann Publishers, Inc., 1989.