Learning a subclass of k-quasi-Horn formulas with membership queries

✍ Scribed by Víctor Lavín Puente

Book ID: 108154759
Publisher: Elsevier Science
Year: 2011
Tongue: English
Weight: 146 KB
Volume: 111
Category: Article
ISSN: 0020-0190
DOI: 10.1016/j.ipl.2011.03.008

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Fast Learning of k-Term DNF Formulas wit

Fast Learning of k-Term DNF Formulas with Queries

✍ A. Blum; S. Rudich 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 649 KB

This paper presents an algorithm that uses equivalence and membership queries to learn the class of \(k\)-term DNF formulas in time \(n \cdot 2^{o(k)}\), where \(n\) is the number of input variables. This improves upon previous \(O\left(n^{k}\right)\) bounds and allows one to learn DNF formulas of \