Generalized notions of mind change complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Generalized notions of mind change complexity

Full text

Pdf (798 KB)

Source

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

Nashville, Tennessee, United States

Pages: 96 - 108

Year of Publication: 1997

ISBN:0-89791-891-6

Authors

Arun Sharma	School of Computer Science and Engineering, University of New South Wales, Sydney, NSW, 2052, Australia
Frank Stephan	Mathematisches Institut, Universität Heidelberg, Im Neuenheimer Feld 294, 69120 Heidelberg, Germany
Yuri Ventsov	School of Computer Science and Engineering, University of New South Wales, Sydney, NSW, 2052, Australia

Sponsors

AT&T Labs :
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
Vanderbilt University : Vanderbilt University

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 20, Citation Count: 5

Additional Information:

references cited by 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/267460.267485 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.

	1	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
	2	Dana Angluin: Inductive Inference of Formal Languages from Positive Data, Information and Control 45 (1980) 117-135.
	3	Janis Barzdins and Rusins Preivalds: Prediction and Limiting Synthesis of Recursively Enumerable Classes of Functions. In: Theory of Algorithms and Programs, Vol. 1 (Latvian State University, edited by Janis Barzdins, Riga 1974) 112-128 (in Russian).
	4	Lenore Blum and Manuel Blum: Toward a mathematical Theory of Inductive Inference. Information and Control, 28 (1975) 125-155.
	5	John Case and Carl H. Smith: Comparison of Identification Criteria for Machine Inductive Inference. Theoretical Computer Science 25 (1983) 193-220.
	6	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]
	7	E. Mark Gold: Language Identification in the Limit. Information and Control, 10 (1967) 447-474.
	8	Klaus P. Jantke, Monotonic and non-monotonic inductive inference, New Generation Computing, v.8 n.4, p.349-360, 1991 [doi>10.1007/BF03037092]
	9	Sanjay Jain , Arun Sharma, Elementary formal systems, intrinsic complexity, and procrastination, Proceedings of the ninth annual conference on Computational learning theory, p.181-192, June 28-July 01, 1996, Desenzano del Garda, Italy [doi>10.1145/238061.238093]
	10	Sanjay Jain and Arun Sharma: Mind Change Complexity of Learning Logic Programs. Under preparation.
	11	Dick de Jongh , Makoto Kanazawa, Angluin's theorem for indexed families of r.e. sets and applications, Proceedings of the ninth annual conference on Computational learning theory, p.193-204, June 28-July 01, 1996, Desenzano del Garda, Italy [doi>10.1145/238061.238095]
	12	Shyam Kapur, Monotonic Language Learning, Proceedings of the Third Workshop on Algorithmic Learning Theory, p.147-158, October 20-22, 1992
	13	Shyam Kapur, Language Learning under Various Types of Constraint Combinations, Proceedings of the 4th International Workshop on Analogical and Inductive Inference: Algorithmic Learning Theory, p.365-378, October 10-15, 1994
	14	Efim Kinber and Thomas Zeugmann: Inductive inference of almost everywhere correct programs by reliably working strategies. Elektronische Informationsverarbeitung und Kybernetik 21 (1985) 91-100.
	15	Steffen Lange , Thomas Zeugmann, Types of monotonic language learning and their characterization, Proceedings of the fifth annual workshop on Computational learning theory, p.377-390, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130427]
	16	Steffen Lange , Thomas Zeugmann, Monotonic Versus Nonmonotonic Language Learning, Proceedings of the Second International Workshop on Nonmonotonic and Inductive Logic, p.254-269, December 02-06, 1991
	17	Steffen Lange , Thomas Zeugmann, Language learning in dependence on the space of hypotheses, Proceedings of the sixth annual conference on Computational learning theory, p.127-136, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168320]
	18	Steffen Lange , Thomas Zeugmann, Language Learning with a Bounded Number of Mind Changes, Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, p.682-691, February 25-27, 1993
	19	Wolfgang Merkle , Frank Stephan, Trees and learning, Proceedings of the ninth annual conference on Computational learning theory, p.270-279, June 28-July 01, 1996, Desenzano del Garda, Italy [doi>10.1145/238061.238118]
	20	Piergiorgio Odifreddi: Classical recursion theory. North-Holland, Amsterdam, 1989.
	21	Daniel N. Osherson, Michael Stob and Scott Weinstein: Systems that learn. Bradford / MIT Press, London, 1986.
	22	Karlis Podnieks: Comparing Various Concepts of Function Prediction, Theory of Algorithms and Programs, Latvian State University, Riga, 210:68- 81,1974.
	23	Gerald E. Sacks, Higher recursion theory, Springer-Verlag New York, Inc., New York, NY, 1990
	24	Rolf Wiehagen, A Thesis in Inductive Inference, Proceedings of the 1st International Workshop on Nonmonotonic and Inductive Logic, p.184-207, December 04-07, 1990

CITED BY 5

	Sanjay Jain , Arun Sharma, On a generalized notion of mistake bounds, Proceedings of the twelfth annual conference on Computational learning theory, p.249-256, July 07-09, 1999, Santa Cruz, California, United States
	Frank Stephan , Yuri Ventsov, Learning algebraic structures from text, Theoretical Computer Science, v.268 n.2, p.221-273, 17 October 2001
	Sanjay Jain , Arun Sharma, Mind change complexity of learning logic programs, Theoretical Computer Science, v.284 n.1, p.143-160, 6 July 2002
	Sanjay Jain , Frank Stephan , Sebastiaan A. Terwijn, Counting extensional differences in BC-learning, Information and Computation, v.188 n.1, p.127-142, 10 January 2004
	Eric Martin , Arun Sharma , Frank Stephan, On the data consumption benefits of accepting increased uncertainty, Theoretical Computer Science, v.382 n.3, p.170-182, September, 2007