On the learnability of Zn-DNF formulas (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the learnability of Zn-DNF formulas (extended abstract)

Full text

Pdf (742 KB)

Source

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

Santa Cruz, California, United States

Pages: 198 - 205

Year of Publication: 1995

ISBN:0-89791-723-5

Authors

Nader H. Bshouty	Department of Computer Science, the University of Calgary, 2500 University Drive N. W., Calgary, Alberta T2N 1N4, Canada
Zhixiang Chen	Department of Computer Science, Boston University, Boston, MA
Scott E. Decatur	Aiken Computation Laboratory, Harvard University, Cambridge, MA
Steven Homer	Department of Computer Science, Boston University, Boston, MA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
University of California : University of California

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/225298.225322 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.

	A88	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	AHK93	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]
	BCF95	Alberto Bertoni , Nicolò Cesa-Bianchi , Guido Fiorino, Efficient learning with equivalence queries of conjunctions of modulo functions, Information Processing Letters, v.56 n.1, p.15-17, Oct. 13, 1995 [doi>10.1016/0020-0190(95)00126-W]
	B94	A. Blum, Personal Communications, 1994.
	BR92	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]
	BCJ93	Avrim Blum , Prasad Chalasani , Jeffrey Jackson, On learning embedded symmetric concepts, Proceedings of the sixth annual conference on Computational learning theory, p.337-346, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168367]
	BS90	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
	B93	N. Bshouty, "Exact Learning via the monotone theory", FOCS, 1993.
	BGHM93	Nader H. Bshouty , Sally A. Goldman , Thomas R. Hancock , Sleiman Matar, Asking questions to minimize errors, Proceedings of the sixth annual conference on Computational learning theory, p.41-50, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168310]
	BHH92a	Nader H. Bshouty , Thomas R. Hancock , Lisa Hellerstein, Learning arithmetic read-once formulas, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.370-381, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129747]
	BHH92b	Nader H. Bshouty , Thomas R. Hancock , Lisa Hellerstein, Learning Boolean read-once formulas with arbitrary symmetric and constant fan-in gates, Proceedings of the fifth annual workshop on Computational learning theory, p.1-15, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130386]
	C95	Zhixiang Chen, Disjunctions of Negated Counting Functions Are Efficiently Learnable with Equivalence Queries, Proceedings of the First Annual International Conference on Computing and Combinatorics, p.344-349, August 24-26, 1995
	CH94	Zhixiang Chen , Steven Homer, On learning counting functions with queries, Proceedings of the seventh annual conference on Computational learning theory, p.218-227, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181116]
	HH91	Thomas Hancock , Lisa Hellerstein, Learning read-once formulas over fields and extended bases, Proceedings of the fourth annual workshop on Computational learning theory, p.326-336, August 05-07, 1991, Santa Cruz, California, United States
	HSW92	David Helmbold , Robert Sloan , Manfred K. Warmuth, Learning integer lattices, SIAM Journal on Computing, v.21 n.2, p.240-266, April 1992 [doi>10.1137/0221019]
	R94	R. Rivest, Personal Communications, 1994.
	SS93	Robert E. Schapire , Linda M. Sellie, Learning sparse multivariate polynomials over a field with queries and counterexamples, Proceedings of the sixth annual conference on Computational learning theory, p.17-26, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168307]
	V84	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]