ON LEARNING MONOTONE DNF FORMULAS UNDER UNIFORM DISTRIBUTIONS

Authors
KUCERA L MARCHETTISPACCAMELA A PROTASI M
Citation
L. Kucera et al., ON LEARNING MONOTONE DNF FORMULAS UNDER UNIFORM DISTRIBUTIONS, Information and computation, 110(1), 1994, pp. 84-95
Citations number
22
Categorie Soggetti
Information Science & Library Science",Mathematics,"Computer Science Information Systems
Journal title
Information and computation → ACNP
ISSN journal
08905401
Volume
110
Issue
1
Year of publication
1994
Pages
84 - 95
Database
ISI
SICI code
0890-5401(1994)110:1<84:OLMDFU>2.0.ZU;2-4
Abstract
We show how to learn in polynomial time monotone d-term DNF formulae ( formulae in disjunctive normal form with at most d terms) using positi ve examples drawn from a distribution that is a generalization of the uniform distribution. (C) 1994 Academic Press, Inc.