Linear time deterministic learning of k-term DNF

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Linear time deterministic learning of k-term DNF

Full text

Pdf (318 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: 37 - 40

Year of Publication: 1993

ISBN:0-89791-611-5

Author

Ulf Berggren

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): 1, Downloads (12 Months): 9, Citation Count: 6

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/168304.168309 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 , Leonard Pitt, Exact learning of read-k disjoint DNF and not-so-disjoint DNF, Proceedings of the fifth annual workshop on Computational learning theory, p.71-76, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130393]
	2	D.Angluin, Learning k-term DNF formulas using queries and counterexamples. Technical Report YALEU/DCS/RR-559, Yale University Department of Computer Science, 1987.
	3	Avrim Blum , Steven Rudich, Fast learning of k-term DNF formulas with queries, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.382-389, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129748]
	4	Avrim Blum , Mona Singh, Learning functions of k terms, Proceedings of the third annual workshop on Computational learning theory, p.144-153, August 06-08, 1990, Rochester, New York, United States
	5	J. Naor , M. Naor, Small-bias probability spaces: efficient constructions and applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.213-223, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100244]
	6	Leonard Pitt , Leslie G. Valiant, Computational limitations on learning from examples, Journal of the ACM (JACM), v.35 n.4, p.965-984, Oct. 1988 [doi>10.1145/48014.63140]
	7	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]

CITED BY 6

	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
	Robert H. Sloan , György Turán, Learning with queries but incomplete information (extended abstract), Proceedings of the seventh annual conference on Computational learning theory, p.237-245, July 12-15, 1994, New Brunswick, New Jersey, United States
	Víctor Dalmau, A dichotomy theorem for learning quantified Boolean formulas, Proceedings of the tenth annual conference on Computational learning theory, p.193-200, July 06-09, 1997, Nashville, Tennessee, United States
	Víictor Dalmau, A Dichotomy Theorem for Learning Quantified Boolean Formulas, Machine Learning, v.35 n.3, p.207-224, June 1999
	Lisa Hellerstein , Vijay Raghavan, Exact learning of DNF formulas using DNF hypotheses, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Lisa Hellerstein , Vijay Raghavan, Exact learning of DNF formulas using DNF hypotheses, Journal of Computer and System Sciences, v.70 n.4, p.435-470, June 2005

INDEX TERMS

Primary Classification:
I. Computing Methodologies
I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
F. Theory of Computation
F.1 COMPUTATION BY ABSTRACT DEVICES
F.1.2 Modes of Computation
Subjects: Probabilistic computation

General Terms:
Algorithms, Theory, Verification

Adobe Acrobat

QuickTime

Windows Media Player

Real Player