Learning &mgr;-branching programs with queries

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Learning &mgr;-branching programs with queries

Full text

Pdf (1.12 MB)

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: 27 - 36

Year of Publication: 1993

ISBN:0-89791-611-5

Authors

Vijay Raghavan
Dawn Wilkins

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

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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.168308 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.

	AFP90	D. Angluin, M. Frazier, and L. Pitt. Learning Conjunctions of Horn Clauses. Proceedzngs of the 31st Annual IEEE Symposzum on the Foundatwns of Computer Science, 1990.
	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]
	Ang88	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	Ang90	Dana Angluin, Negative Results for Equivalence Queries, Machine Learning, v.5 n.2, p.121-150, Jun. 1990 [doi>10.1023/A:1022692615781]
	BHH92	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]
	Bry92	Randal E. Bryant, Symbolic Boolean manipulation with ordered binary-decision diagrams, ACM Computing Surveys (CSUR), v.24 n.3, p.293-318, Sept. 1992 [doi>10.1145/136035.136043]
	FHS78	Steven Fortune , John E. Hopcroft , Erik Meineche Schmidt, The Complexity of Equivalence and Containment for Free Single Variable Program Schemes, Proceedings of the Fifth Colloquium on Automata, Languages and Programming, p.227-240, July 17-21, 1978
	Han90	Thomas R. Hancock, Identifying μ-formula decision trees with queries, Proceedings of the third annual workshop on Computational learning theory, p.23-37, August 06-08, 1990, Rochester, New York, United States
	Han92	Thomas Raysor Hancock, The complexity of learning formulas and decision trees that have restricted reads, Harvard University, Cambridge, MA, 1992
	Mei89	Christoph Meinel, Modified branching programs and their computational power, Springer-Verlag New York, Inc., New York, NY, 1989
	RS90	Vijay Raghavan , Stephen R. Schach, Learning switch configurations, Proceedings of the third annual workshop on Computational learning theory, p.38-51, August 06-08, 1990, Rochester, New York, United States
	Tar83	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	Weg87	Ingo Wegener, The complexity of Boolean functions, John Wiley & Sons, Inc., New York, NY, 1987

CITED BY 3

	Nader H. Bshouty , Christino Tamon , David K. Wilson, On learning width two branching programs (extended abstract), Proceedings of the ninth annual conference on Computational learning theory, p.224-227, June 28-July 01, 1996, Desenzano del Garda, Italy
	Richard Nock , Tapio Elomaa , Matti Kääriäinen, Reduced error pruning of branching programs cannot be approximated to within a logarithmic factor, Information Processing Letters, v.87 n.2, p.73-78, 31 July 2003
	Atsuyoshi Nakamura, An efficient query learning algorithm for ordered binary decision diagrams, Information and Computation, v.201 n.2, p.178-198, September 15, 2005