Learning conjunctions of two unate DNF formulas (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Learning conjunctions of two unate DNF formulas (extended abstract): computational and informational results

Full text

Pdf (1.05 MB)

Source

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

Desenzano del Garda, Italy

Pages: 255 - 265

Year of Publication: 1996

ISBN:0-89791-811-8

Authors

Aaron Feigelson	Department of EECS, Northwestern University, Evanston, IL
Lisa Hellerstein	Department of EECS, Northwestern University, Evanston, IL

Sponsors

Univ degli Studi de Milano : Universite degli Studi de Milano
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): 17, Downloads (12 Months): 21, Citation Count: 0

Additional Information:

references index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/238061.238112 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	Howard Aizenstein , Tibor Hegedűs , Lisa Hellerstein , Leonard Pitt, Complexity theoretic hardness results for query learning, Computational Complexity, v.7 n.1, p.19-53, Jul. 1998 [doi>10.1007/PL00001593]
	2	D. Angluin. Learning k-term dnf formulas using queries and counterexamples. Technical Report YALE/DCS/RR-559, Yale University, ~987.
	3	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	4	Dana Angluin, Computational learning theory: survey and selected bibliography, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.351-369, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129746]
	5	Dana Angluin , Lisa Hellerstein , Marek Karpinski, Learning read-once formulas with queries, Journal of the ACM (JACM), v.40 n.1, p.185-210, Jan. 1993 [doi>10.1145/138027.138061]
	6	N. Bshouty. Exact learning via the monotone theory. In Proceedings of the 34th Annual Symposium on Foundations of Computer Science, pages 302-311, Los Alamitos, CA, November 1993. IEEE Computer Society Press.
	7	O. Ekin, P. Hammer, and U. Peled. Horn functions and submodular boolean functions. Technical Report RRR!-95, Rutgers Center for Operations Research, January 1995.
	8	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	9	Lisa Hellerstein , Vijay Raghavan , Krishnan Pillaipakkamnatt , Dawn Wilkins, How many queries are needed to learn?, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.190-199, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225114]
	10	Krishnan Pillaipakkamnatt , Vijay Raghavan, On the limits of proper learnability of subclasses of DNF formulas, Proceedings of the seventh annual conference on Computational learning theory, p.118-129, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181063]