On learning bounded-width branching programs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On learning bounded-width branching programs

Full text

Pdf (882 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: 361 - 368

Year of Publication: 1995

ISBN:0-89791-723-5

Authors

Funda Ergün	Department of Computer Science, Cornell University, Ithaca, NY
S. Ravi Kumar	Department of Computer Science, Cornell University, Ithaca, NY
Ronitt Rubinfeld	Department of Computer Science, Cornell University, Ithaca, NY

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

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.225342 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	Naoki Abe , Manfred K. Warmuth, On the Computational Complexity of Approximating Distributions by Probabilistic Automata, Machine Learning, v.9 n.2-3, p.205-260, July 1992 [doi>10.1007/BF00992677]
	2	D. Angluin. On the Complexity of Minimum Inference of Regular Sets. Information and Control, 39:337-350, 1978.
	3	D. Angluin. A Note on the Number of Queries Needed to Identify Regular Languages. Information and Control, 51:76-87, 1981.
	4	Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
	5	Dana Angluin , Philip Laird, Learning From Noisy Examples, Machine Learning, v.2 n.4, p.343-370, April 1988 [doi>10.1023/A:1022873112823]
	6	David A. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, Journal of Computer and System Sciences, v.38 n.1, p.150-164, February 1989 [doi>10.1016/0022-0000(89)90037-8]
	7	Allan Borodin , Danny Dolev , Faith E Fich , Wolfgang Paul, Bounds for width two branching programs, SIAM Journal on Computing, v.15 n.2, p.549-560, May 1986 [doi>10.1137/0215040]
	8	Yoav Freund , Michael Kearns , Dana Ron , Ronitt Rubinfeld , Robert E. Schapire , Linda Sellie, Efficient learning of typical finite automata from random walks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.315-324, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167191]
	9	E. Gold. Complexity of Automaton Identification from Given Data. Information and Control, 37:302-320, 1978.
	10	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]
	11	M. Kearns , M. Li , L. Pitt , L. Valiant, On the learnability of Boolean formulae, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.285-295, January 1987, New York, New York, United States [doi>10.1145/28395.28426]
	12	Michael Kearns , Yishay Mansour , Dana Ron , Ronitt Rubinfeld , Robert E. Schapire , Linda Sellie, On the learnability of discrete distributions, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.273-282, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195155]
	13	M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
	14	Leonard Pitt , Manfred K. Warmuth, Prediction-preserving reducibility, Journal of Computer and System Sciences, v.41 n.3, p.430-467, Dec. 1990 [doi>10.1016/0022-0000(90)90028-J]
	15	Leonard Pitt , Manfred K. Warmuth, The minimum consistent DFA problem cannot be approximated within any polynomial, Journal of the ACM (JACM), v.40 n.1, p.95-142, Jan. 1993 [doi>10.1145/138027.138042]
	16	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]
	17	R. Rivest and S. Schapire. Diversity-based Inference of Finite Automata. In Proc. 28th FOCS, pages 78-87. IEEE, 1987.
	18	R. L. Rivest , R. E. Schapire, Inference of finite automata using homing sequences, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.411-420, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73047]
	19	Dana Ron , Ronitt Rubinfeld, Learning fallible finite state automata, Proceedings of the sixth annual conference on Computational learning theory, p.218-227, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168336]
	20	D. Ron, Y. Singer, and N. Tishby. The Power of Amnesia. In Advances in Neural Information Processing Systems, Volume 6, Morgan Kauffman, 1993.
	21	D. Ron, Y. Singer, and N. Tishby. On the Learnability and Usage of Acyclic Probabilistic Finite Automata. Manuscript, January 1995.
	22	R. Schapire. Personal Communication. 1995.
	23	R. Schapire and M. Wannuth. Personal Communication. 1990.
	24	Hinrich Schütze , Yoram Singer, Part-of-speech tagging using a Variable Memory Markov model, Proceedings of the 32nd annual meeting on Association for Computational Linguistics, p.181-187, June 27-30, 1994, Las Cruces, New Mexico [doi>10.3115/981732.981757]

CITED BY 4

	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
	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
	Dana Ron , Ronitt Rubinfeld, Exactly Learning Automata of Small Cover Time, Machine Learning, v.27 n.1, p.69-96, April 1997
	William W. Cohen, Hardness Results for Learning First-Order Representations and Programming by Demonstration, Machine Learning, v.30 n.1, p.57-87, Jan. 1998