On a generalized notion of mistake bounds

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On a generalized notion of mistake bounds

Full text

Pdf (930 KB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the twelfth annual conference on Computational learning theory table of contents

Santa Cruz, California, United States

Pages: 249 - 256

Year of Publication: 1999

ISBN:1-58113-167-4

Authors

Sanjay Jain	School of Computing, National University of Singapore, Singapore 119260, Republic of Singapore
Arun Sharma	School of Computer Science and Engineering, The University of New South Wales, Sydney, NSW 2052, Australia

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
Univ. of California, : University of California at Santa Cruz

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 9, Citation Count: 0

Additional Information:

references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/307400.307450 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AFS96	Andris Ambainis , Rusins Freivalds , Carl H. Smith, General Inductive Inference Types Based on Linearly-Ordered Sets, Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, p.243-253, February 22-24, 1996
	AJS97	Andris Ambainis , Sanjay Jain , Arun Sharma, Ordinal Mind Change Complexity of Language Identification, Proceedings of the Third European Conference on Computational Learning Theory, p.301-315, March 17-19, 1997
	Ang80a	D. Angluin. Finding patterns common to a set of strings. Journal of Computer and System Sciences, 21:46-62, 1980.
	Ang80b	D. Angluin. Inductive inference of formal languages from positive data. Information and Control, 45:117-135, 1980.
	AS94	H. Arimura and T. Shinohara. Inductive inference of Prolog programs with linear data dependency from positive data. In H. Jaakkola, H. Kangassalo, T. Kitahashi, and A. Markus, editors, Proc. Information Modelling and Knowledge Bases V, pages 365-375. IOS Press, 1994.
	BF72	J. Barzdir/~ and R. Freivalds. On the prediction of general recursive functions. Soviet Mathematics Doklady, 13:1224-1228, 1972.
	CJNM94	J. Case, S. Jain, and S. Ngo Manguelle. Refinements of inductive inference by Popperian and reliable machines. Kybernetika, 30:23-52, 1994.
	CJS95	John Case , Mandayam Suraj , Sanjay Jain, Not-So-Nearly-Minimal-Size Program Inference, Algorithmic Learning for Knowledge-Based Systems, GOSLER Final Report, p.76-95, January 1995
	FS93	Rūsiņš Freivalds , Carl H. Smith, On the role of procrastination in machine learning, Information and Computation, v.107 n.2, p.237-271, Dec. 1993 [doi>10.1006/inco.1993.1068]
	JS97	Sanjay Jain , Arun Sharma, Elementary formal systems, intrinsic complexity, and procrastination, Information and Computation, v.132 n.1, p.65-84, Jan. 10, 1997 [doi>10.1006/inco.1996.2614]
	JS99	Sanjay Jain , Arun Sharma, Mind Change Complexity of Learning Logic Programs, Proceedings of the 4th European Conference on Computational Learning Theory, p.198-213, March 29-31, 1999
	Kle38	S. Kleene. Notations for ordinal numbers. Journal of Symbolic Logic, 3:150-155, 1938.
	KR96	M. R. K. Krishna Rao, A Class of Prolog Programs Inferable from Positive Data, Proceedings of the 7th International Workshop on Algorithmic Learning Theory, p.272-284, October 23-25, 1996
	KS97	Susanne Kaufmann , Frank Stephan, Resource bounded next value and explanatory identification: learning automata, patterns and polynomials on-line, Proceedings of the tenth annual conference on Computational learning theory, p.263-274, July 06-09, 1997, Nashville, Tennessee, United States [doi>10.1145/267460.267509]
	Lit88	Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
	Llo87	J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
	MSS91	S Miyano, A. Shinohara, and T. Shinohara. Which cl~Lsses of elementary formal systems are polynomial-time learnable? In Proceedings of the Second Workshop on Algorithmic Learning Theory, pages 139-150, 1991.
	MSS93	S. Miyano, A. Shinohara, and T. Shinohara. Learning elementary formal systems and an application to discovering motifs in proteins. Technical Report RIFIS-TRCS-37, RIFIS, Kyushu University, 1993.
	MY78	Michael Machtey , Paul Young, An Introduction to the General Theory of Algorithms, Elsevier Science Inc., New York, NY, 1978
	Rog67	Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
	Sac90	Gerald E. Sacks, Higher recursion theory, Springer-Verlag New York, Inc., New York, NY, 1990
	Sha81a	E. Shapiro. A general incremental algorithm that infers theory from facts. In International Joint Conference on Artificial Intelligence, 1981.
	Sha81b	E. Shapiro. Inductive inference of theories from facts. Technical Report 192, Computer Science Department, Yale University, 1981.
	Shi91	Takeshi Shinohara, Inductive inference of monotonic formal systems from positive data, New Generation Computing, v.8 n.4, p.371-384, 1991 [doi>10.1007/BF03037094]
	SSV97	Arun Sharma , Frank Stephan , Yuri Ventsov, Generalized notions of mind change complexity, Proceedings of the tenth annual conference on Computational learning theory, p.96-108, July 06-09, 1997, Nashville, Tennessee, United States [doi>10.1145/267460.267485]
	Wri89	Keith Wright, Identification of unions of languages drawn from an identifiable class, Proceedings of the second annual workshop on Computational learning theory, p.328-333, December 1989, Santa Cruz, California, United States
	WZ95	Rolf Wiehagen , Thomas Zeugmann, Learning and Consistency, Algorithmic Learning for Knowledge-Based Systems, GOSLER Final Report, p.1-24, January 1995