Article

Free access

Learning Sat-k-DNF formulas from membership queries

Authors:

F. Bergadano,

D. Catalano,

S. VarricchioAuthors Info & Claims

STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing

Pages 126 - 130

https://doi.org/10.1145/237814.237845

Published: 01 July 1996 Publication History

PDF eReader

References

[1]

D. Angluin. Learning regular sets from queries and cotmterexamples. Information and Computation, 75:87- 106, 1987.

Digital Library

Google Scholar

[2]

F. Bergadano and S. Varricchio. Learning Behaviors of Automata from Multiplicity and Equivalence Queries. SiAM J. Computing, to appear. Abstract available in LNCS 778, pages 54-62, 1994.

Digital Library

Google Scholar

[3]

J. Berstel and C. Reutenauer. Rational series and their languages. Springer-Verlag, Berlin, 1988.

Digital Library

Google Scholar

[4]

N. H. Bshouty. Exact Learning Boolean Functions via the Monotone Theory. In Proc. Syrup. on the Foundations of Computer Science (FOC$), 1993.

Google Scholar

[5]

N. H. Bshouty and Y. Mansour. Simple Learning Algorithms for Decision Trees and Multivariate Polynomials.

Google Scholar

[6]

A. Ehrenfeucht and D. Haussler. Learning decision trees from random examples. Information and computation, 82:231-246, 1989.

Digital Library

Google Scholar

[7]

S. Eilenberg. Automata Languages and Machines, Vol. A, Academic Press, New York, 1974.

Digital Library

Google Scholar

[8]

J. E. Hopcroft and J. D. UUman. Introduction to Automata Theory Languages and Computation, Addison- Wesley, Reading, MA, 1979.

Digital Library

Google Scholar

[9]

J. Jackson. An efficient membership query algorithm for learning DNF with respect to the uniform distribution. In Proc. Syrnp. on the Foundations of Computer Science (FOCS), 1994.

Digital Library

Google Scholar

[10]

E. Kushilevitz and Y. Mansour. Learning Decision Trees using the Fourier Spectrum. SIAM J. Computing, 22(6):1331-1348, 1993.

Digital Library

Google Scholar

[11]

B. K. Natarajan. Machine Learning. Morgan KaufmaIm Publishers, inc.

Google Scholar

[12]

L. Pitt and M. K. Warmuth. Prediction-preserving reducibility. Journal of Computer and System Science, 41(3):430-467, 1990.

Digital Library

Google Scholar

[13]

A. Salomaa and M. Soittola. Automata theoretic aspects of formal power series. Springer-Verlag, New York, 1978.

Digital Library

Google Scholar

[14]

R.E. Shapire, L. M. Sellie. Learning sparse multivariate polynomials over a field with queries and counterexamples. In Proceedings of the Sixth Annual A CM Workshop on Computational Learning Theory. July 1993.

Digital Library

Google Scholar

[15]

L. G. Valiant. A theory of learnable. Communications of the ACM, 27(11):1134-1142, 1984.

Digital Library

Google Scholar

Cited By

View all

Thon MJaeger H(2015)Links between multiplicity automata, observable operator models and predictive state representationsThe Journal of Machine Learning Research10.5555/2789272.278927616:1(103-147)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.5555/2789272.2789276
Varricchio S(2015)Learning AutomataEncyclopedia of Algorithms10.1007/978-3-642-27848-8_194-2(1-7)Online publication date: 20-Feb-2015
https://doi.org/10.1007/978-3-642-27848-8_194-2
de Luca A(2009)Stefano Varricchio (1960–2008)Semigroup Forum10.1007/s00233-009-9201-x80:1(1-7)Online publication date: 19-Dec-2009
https://doi.org/10.1007/s00233-009-9201-x
Show More Cited By

Index Terms

Learning Sat-k-DNF formulas from membership queries
1. Computing methodologies
  1. Machine learning
2. Theory of computation
  1. Formal languages and automata theory

Recommendations

Learning with errors in answers to membership queries

We study the learning models defined in [D. Angluin, M. Krikis, R.H. Sloan, G. Turan, Malicious omissions and errors in answering to membership queries, Machine Learning 28 (2-3) (1997) 211-255]: Learning with equivalence and limited membership queries ...
Exact learning of DNF formulas using DNF hypotheses
Special issue on COLT 2002

We show the following: (a) For any @e>0, log^(^3^+^@e^)n-term DNF cannot be polynomial-query learned with membership and strongly proper equivalence queries. (b) For sufficiently large t, t-term DNF formulas cannot be polynomial-query learned with ...
Certain classes of polynomial expansions and multiplication formulas

The authors first present a class of expansions in a series of Bernoulli polyomials and then show how this general result can be applied to yield various (known or new) polynomial expansions. The corresponding expansion problem involving the Euler ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing

July 1996

661 pages

ISBN:0897917855

DOI:10.1145/237814

Chairman:
Gary L. Miller

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 July 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC96

Sponsor:

SIGACT

STOC96: ACM Symposium on Theory of Computing

May 22 - 24, 1996

Pennsylvania, Philadelphia, USA

Acceptance Rates

STOC '96 Paper Acceptance Rate 74 of 201 submissions, 37%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
386
Total Downloads

Downloads (Last 12 months)79
Downloads (Last 6 weeks)10

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Thon MJaeger H(2015)Links between multiplicity automata, observable operator models and predictive state representationsThe Journal of Machine Learning Research10.5555/2789272.278927616:1(103-147)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.5555/2789272.2789276
Varricchio S(2015)Learning AutomataEncyclopedia of Algorithms10.1007/978-3-642-27848-8_194-2(1-7)Online publication date: 20-Feb-2015
https://doi.org/10.1007/978-3-642-27848-8_194-2
de Luca A(2009)Stefano Varricchio (1960–2008)Semigroup Forum10.1007/s00233-009-9201-x80:1(1-7)Online publication date: 19-Dec-2009
https://doi.org/10.1007/s00233-009-9201-x
Bisht LBshouty NMazzawi H(2006)On optimal learning algorithms for multiplicity automataProceedings of the 19th annual conference on Learning Theory10.1007/11776420_16(184-198)Online publication date: 22-Jun-2006
https://dl.acm.org/doi/10.1007/11776420_16
Bshouty NTamon CWilson D(2005)Learning matrix functions over ringsComputational Learning Theory10.1007/3-540-62685-9_4(27-37)Online publication date: 3-Jun-2005
https://doi.org/10.1007/3-540-62685-9_4
Beimel AKushilevitz E(2005)Learning boxes in high dimensionComputational Learning Theory10.1007/3-540-62685-9_2(3-15)Online publication date: 3-Jun-2005
https://doi.org/10.1007/3-540-62685-9_2
Bergadano FBshouty NTamon CVarricchio S(2005)On learning branching programs and small depth circuitsComputational Learning Theory10.1007/3-540-62685-9_13(150-161)Online publication date: 3-Jun-2005
https://doi.org/10.1007/3-540-62685-9_13
Bshouty NBurroughs L(2003)On the proper learning of axis-parallel conceptsThe Journal of Machine Learning Research10.1162/1532443043229726764(157-176)Online publication date: 1-Dec-2003
https://dl.acm.org/doi/10.1162/153244304322972676
Melideo GVarricchio S(2002)Learning Unary Output Two-Tape Automata from Multiplicity and Equivalence QueriesAlgorithmic Learning Theory10.1007/3-540-49730-7_7(87-102)Online publication date: 24-Sep-2002
https://doi.org/10.1007/3-540-49730-7_7
Bshouty NBurroughs L(2002)On the Proper Learning of Axis Parallel ConceptsComputational Learning Theory10.1007/3-540-45435-7_20(287-302)Online publication date: 25-Jun-2002
https://doi.org/10.1007/3-540-45435-7_20
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

Learning with errors in answers to membership queries

Exact learning of DNF formulas using DNF hypotheses

Certain classes of polynomial expansions and multiplication formulas