On the structure of degrees of inferability

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the structure of degrees of inferability

Full text

Pdf (989 KB)

Source

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

Santa Cruz, California, United States

Pages: 117 - 126

Year of Publication: 1993

ISBN:0-89791-611-5

Authors

Martin Kummer
Frank Stephan

Sponsors

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): 4, Downloads (12 Months): 18, Citation Count: 3

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/168304.168319 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	L. Adleman, M. Blum. Inductive inference and unsolvability. Journal of Symbohc Logic, 56:891-900, 1991.
	2	L Blum, M. Blum. Towards a mathematicaltheory of inductive inference. Information and Control. 28 125-155, 1975
	3	Richard Beigel , William I. Gasarch , John Gill , James C. Owings, Terse, superterse, and verbose sets, Information and Computation, v.103 n.1, p.68-85, March 1993 [doi>10.1006/inco.1993.1014]
	4	J. Case. S. Jain, A. Sharma. On learning limiting programs. {nternatwnal Journal on Foundat,ons of Computer Science, 3:93-115, 1992.
	5	J. Case. C. Smith. Identification criteria for machine inductive mference. Theoretical Computer Sc,ence, 25:193-220, 1983.
	6	Peter Cholak , Efim Kinber , Rod Downey , Martin Kummer , Lance Fortnow , Stuart Kurtz , William Gasarch , Theodore A. Slaman, Degrees of inferability, Proceedings of the fifth annual workshop on Computational learning theory, p.180-192, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130406]
	7	R. Epstein, R. Haas, R. Kramer. Hierarchies of sets and degrees below 0'. In: Logic Year 1979-80, Lecture Notes m Mathematics, Vol. 859, Springer- Verlag, Berlin, 1981.
	8	L. Fortnow, W Gasarch, S. Jain, E. Kinber, M. Kummer, S. Kurtz, M. Pleszkoch, T. Slaman. R. Solovay, F. Stephan. Extremes in the degrees of mferability. Submitted for publication, 1993.
	9	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
	10	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]
	11	E. Gold. Language identification m the hmit. In- /ormatwn and Control, 10:447-474, 1967
	12	C. Haught. The degrees below a 1-generic degree < 0~. Journal of Symbohc Logic, 51:770-777, 1986.
	13	Sanjay Jain , Arun Sharma, On the non-existence of maximal inference degrees for language identification, Information Processing Letters, v.47 n.2, p.81-88, Aug. 20, 1993 [doi>10.1016/0020-0190(93)90229-3]
	14	C. Jockusch. Degrees of generic sets. In: Recurszon Theory: Its Generahzatzons and Apphcatzons. Cambridge University Press, 1980.
	15	Efim B. Kinber, Some problems of learning with an oracle, Proceedings of the third annual workshop on Computational learning theory, p.178-186, August 06-08, 1990, Rochester, New York, United States
	16	M. Kumabe. A l-generic degree which bounds a minimal degree. Journal of Symbohc ~og~c, 55:733- 743, 1990
	17	D. Osherson, M. Stob, S Weinstein. Systems that learn. MIT Press, Cambridge (MA), 1986.
	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	Carl H. Smith, The Power of Pluralism for Automatic Program Synthesis, Journal of the ACM (JACM), v.29 n.4, p.1144-1165, Oct. 1982 [doi>10.1145/322344.322356]
	20	Robert I. Soare, Recursively enumerable sets and degrees, Springer-Verlag New York, Inc., New York, NY, 1987

CITED BY 3

	Martin Kummer, The strength of noninclusions for teams of finite learners (extended abstract), Proceedings of the seventh annual conference on Computational learning theory, p.268-277, July 12-15, 1994, New Brunswick, New Jersey, United States
	Frank Stephan, Learning via queries and oracles, Proceedings of the eighth annual conference on Computational learning theory, p.162-169, July 05-08, 1995, Santa Cruz, California, United States
	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