Article

Free access

Learning μ-branching programs with queries

Authors:

Vijay Raghavan,

Dawn WilkinsAuthors Info & Claims

COLT '93: Proceedings of the sixth annual conference on Computational learning theory

Pages 27 - 36

https://doi.org/10.1145/168304.168308

Published: 01 August 1993 Publication History

PDF eReader

References

[1]

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.

Digital Library

Google Scholar

[2]

D. Angluin, L. Hellerstein, and M. Karpinski. Learning Read-Once Formulas with Queries. Journal of the Association for Computing Machinery, 1993.

Digital Library

Google Scholar

[3]

D. Angluin. Queries and Concept Learning. Machine Learning, 2, 1988.

Digital Library

Google Scholar

[4]

D. Angluin. Negative Results for Equivalence Queries. Machine Learning, 5, 1990.

Digital Library

Google Scholar

[5]

N. Bshouty, T. Hancock, and L. Hellerstein. Learning Boolean Read-Once Formulas with Arbitrary Symmetric and Constant Fan-in Gates. Proceedings of the Fifth Annual Workshop on Computatwnal Learmng Theory, 1992.

Digital Library

Google Scholar

[6]

R. Bryant. Symbolic Boolean Manipulation with Ordered Binary-Decision Diagrams. ACM Computing Surveys, 24(3):293- 318, 1992.

Digital Library

Google Scholar

[7]

S. Fortune, J. Hopcroft, and E. Schmidt. The Complexity of Equivalence and Containment for Free Single Variable Program Schemes. Lecture Notes zn zn Computer Sczence: Automata, Languages Programming, 62:227-240, 1978.

Digital Library

Google Scholar

[8]

T. Hancock. Identifying/~-Formula Decision Trees with Queries. Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990.

Digital Library

Google Scholar

[9]

T. Hancock. The Complexity of Learmng Formulas and Decision Trees that have Restricted Reads. PhD thesis, Harvard University, Center for Research in Computing Technology, Aiken Computation Laboratory, 1992. TR- 15-92.

Digital Library

Google Scholar

[10]

C. Meinel. Lecture Notes in Computer Science. In Modified Branching Programs and their Computational Power. Springer-Verlag, 1989.

Digital Library

Google Scholar

[11]

V. Raghavan and S. Schach. Learning Switch Configurations. Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990.

Digital Library

Google Scholar

[12]

R.E. Tarjan. Data Structures and Network Algorithms, volume 44. SIAM, 1983.

Digital Library

Google Scholar

[13]

I. Wegener. The Complexzty of Boolean Functions. John Wiley and Sons, 1987.

Digital Library

Google Scholar

Cited By

View all

Ron DTsur G(2012)Testing computability by width-two OBDDsTheoretical Computer Science10.1016/j.tcs.2011.11.007420(64-79)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1016/j.tcs.2011.11.007
Brody JMatulef KWu C(2011)Lower bounds for testing computability by small width OBDDsProceedings of the 8th annual conference on Theory and applications of models of computation10.5555/2008967.2009011(320-331)Online publication date: 23-May-2011
https://dl.acm.org/doi/10.5555/2008967.2009011
Brody JMatulef KWu C(2011)Lower Bounds for Testing Computability by Small Width OBDDsTheory and Applications of Models of Computation10.1007/978-3-642-20877-5_32(320-331)Online publication date: 2011
https://doi.org/10.1007/978-3-642-20877-5_32
Show More Cited By

Index Terms

Learning μ-branching programs with queries

Recommendations

A Model for Discussing the Quality of Technology-Enhanced Learning in Blended Learning Programmes

This paper presents a comprehensive model for supporting informed and critical discussions concerning the quality of Technology-Enhanced Learning in Blended Learning programmes. The model aims to support discussions around domains such as how ...
A review of empirical research on blended learning in teacher education programs

Although blended learning has been considered as an important alternative approach that can overcome various limitations related to both face-to-face and online learning, there is relatively limited empirical studies on blended learning approach in ...
Decidable containment of recursive queries
Database theory

One of the most important reasoning tasks on queries is checking containment, i.e., verifying whether one query yields necessarily a subset of the result of another one. Query containment is crucial in several contexts, such as query optimization, query ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

COLT '93: Proceedings of the sixth annual conference on Computational learning theory

August 1993

463 pages

ISBN:0897916115

DOI:10.1145/168304

Editor:
Lenny Pitt
Univ. of Illinois, Urbana

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

6COLT93

Sponsor:

6COLT93: 6th Annual Conference on Computational Learning Theory

July 26 - 28, 1993

California, Santa Cruz, USA

Acceptance Rates

Overall Acceptance Rate 35 of 71 submissions, 49%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
249
Total Downloads

Downloads (Last 12 months)60
Downloads (Last 6 weeks)14

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ron DTsur G(2012)Testing computability by width-two OBDDsTheoretical Computer Science10.1016/j.tcs.2011.11.007420(64-79)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1016/j.tcs.2011.11.007
Brody JMatulef KWu C(2011)Lower bounds for testing computability by small width OBDDsProceedings of the 8th annual conference on Theory and applications of models of computation10.5555/2008967.2009011(320-331)Online publication date: 23-May-2011
https://dl.acm.org/doi/10.5555/2008967.2009011
Brody JMatulef KWu C(2011)Lower Bounds for Testing Computability by Small Width OBDDsTheory and Applications of Models of Computation10.1007/978-3-642-20877-5_32(320-331)Online publication date: 2011
https://doi.org/10.1007/978-3-642-20877-5_32
Ron DTsur G(2010)Testing computability by width-2 OBDDs where the variable order is unknownProceedings of the 7th international conference on Algorithms and Complexity10.1007/978-3-642-13073-1_13(131-142)Online publication date: 26-May-2010
https://dl.acm.org/doi/10.1007/978-3-642-13073-1_13
Ron DTsur G(2009)Testing Computability by Width Two OBDDsProceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques10.1007/978-3-642-03685-9_51(686-699)Online publication date: 21-Aug-2009
https://dl.acm.org/doi/10.1007/978-3-642-03685-9_51
Raghavan VWilkins D(2007)A characterization and nearly linear-time equivalence test forμ-branching programsTheory of Computing Systems10.1007/BF0267946230:3(249-283)Online publication date: 31-Jul-2007
https://doi.org/10.1007/BF02679462
Nakamura A(2005)An efficient query learning algorithm for ordered binary decision diagramsInformation and Computation10.1016/j.ic.2005.05.003201:2(178-198)Online publication date: Sep-2005
https://doi.org/10.1016/j.ic.2005.05.003
Nakamura A(2005)An efficient exact learning algorithm for ordered binary decision diagramsAlgorithmic Learning Theory10.1007/3-540-63577-7_51(307-322)Online publication date: 9-Jun-2005
https://doi.org/10.1007/3-540-63577-7_51
Nakamura A(2005)Query learning of bounded-width OBDDsAlgorithmic Learning Theory10.1007/3-540-61863-5_32(37-50)Online publication date: 3-Jun-2005
https://doi.org/10.1007/3-540-61863-5_32
Gavaldà RGuijarro D(2005)Learning ordered binary decision diagramsAlgorithmic Learning Theory10.1007/3-540-60454-5_41(228-238)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-60454-5_41
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A Model for Discussing the Quality of Technology-Enhanced Learning in Blended Learning Programmes

A review of empirical research on blended learning in teacher education programs

Decidable containment of recursive queries