Aspects of complexity of conservative probabilistic learning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Aspects of complexity of conservative probabilistic learning

Full text

Pdf (1.02 MB)

Source

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

Madison, Wisconsin, United States

Pages: 72 - 78

Year of Publication: 1998

ISBN:1-58113-057-0

Author

Léa Meyer

Institut für Informatik und Gesellschaft, Albert-Ludwigs-Universität Freiburg, 79098 Freiburg, Germany

Sponsors

University of Wisconsin : University of Wisconsin
UC @ Santa Cruz : UC @ Santa Cruz
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms

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/279943.279957 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	D. Angluin, Inductive In.tErence of formal languages from positive data, Information and Control 45 (1980) 117 - 135.
	2	Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
	3	R. Freiwfids, Finite identification of general recursive functions by probabilistic strategies, in: Proc. of the Conf. on Fundamentals of Computation Theory (Akademie-Verlag, Berlin, 1979) 138 - 145.
	4	L. Fortnow, M. Gasarch, S. Jain, E. B. Kinber, M. Kummer, S. Kurtz, M. Pleszkoch, T. Slaman, R. Solovay, E Stephan, Extremes in the degrees in inferability, Ann. Pure Appl. Logic 66 (1994) 231 - 276.
	5	Rūsiņš Freivalds , Efim Kinber , Carl H. Smith, On the intrinsic complexity of learning, Information and Computation, v.123 n.1, p.64-71, Nov. 15, 1995 [doi>10.1006/inco.1995.1158]
	6	William I. Gasarch , Mark G. Pleszkoch, Learning via queries to an oracle, Proceedings of the second annual workshop on Computational learning theory, p.214-229, December 1989, Santa Cruz, California, United States
	7	William I. Gasarch , Carl H. Smith, Learning via queries, Journal of the ACM (JACM), v.39 n.3, p.649-674, July 1992 [doi>10.1145/146637.146670]
	8	E.M. Gold, Language identification in the limit, Information and Control 10 (1967) 447 - 474.
	9	Sanjay Jain , Arun Sharma, On the intrinsic complexity of language identification, Proceedings of the seventh annual conference on Computational learning theory, p.278-286, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181150]
	10	John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	11	Martin Kummer , Frank Stephan, On the structure of degrees of inferability, Journal of Computer and System Sciences, v.52 n.2, p.214-238, April 1996 [doi>10.1006/jcss.1996.0018]
	12	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]
	13	Léa Meyer, Probabilistic Language Learning Under Monotonicity Constraints, Proceedings of the 6th International Conference on Algorithmic Learning Theory, p.169-184, October 18-20, 1995
	14	Léa Meyer, Probabilistic language learning under monotonicity constraints, Theoretical Computer Science, v.185 n.1, p.81-128, Oct. 10, 1997 [doi>10.1016/S0304-3975(97)00017-0]
	15	P. Odifreddi, Classical Recursion lheory, North Holland, 1989.
	16	Daniel N. Osherson , Michael Stob , Scott Weinstein, Systems that learn: an introduction to learning theory for cognitive and computer scientists, MIT Press, Cambridge, MA, 1986
	17	L. Pitt, Probabilistic inductive inference, Journal of the ACM (JACM), v.36 n.2, p.383-433, April 1989 [doi>10.1145/62044.62053]
	18	Theodore A. Slaman , Robert Solovay, When oracles do not help, Proceedings of the fourth annual workshop on Computational learning theory, p.379-383, August 05-07, 1991, Santa Cruz, California, United States
	19	Robert I. Soare, Recursively enumerable sets and degrees, Springer-Verlag New York, Inc., New York, NY, 1987
	20	Frank Stephen, Noisy inference and oracles, Theoretical Computer Science, v.185 n.1, p.129-157, Oct. 10, 1997 [doi>10.1016/S0304-3975(97)00018-2]
	21	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
	22	. Wiehagen, R. Freivalds, E.B. Kinber, On the Power of Probabilistic Strategies in Inductive Inference, Theoretical Computer Science 2g (1984), 111 - 133.
	23	R. Wiehagen, R. Freivalds, E.B. Kinber, Probabilistic versus Deterministic Inductive Inference in Nonstandard Numberings, Zeitschr. f. math. Logik und Grundlagen d. Math. 34 (1988) 531 - 539.
	24	Thomas Zeugmann , Steffen Lange, A Guided Tour Across the Boundaries of Learning Recursive Languages, Algorithmic Learning for Knowledge-Based Systems, GOSLER Final Report, p.190-258, January 1995