Research Note on Decision Lists
Research Note on Decision Lists
复制标题
关于决策列表的研究笔记
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
S. Benson
中科院分区：
文献类型：
--
作者：
Ron Kohavi;S. Benson
在他的文章《学习决策表》中，Rivest证明了(k-DNFCNF)是k-∪的一个真子集。证据基于以下不正确的说法：……如果函数f有大小为t的素蕴涵，则当k<；时，f没有k-dnf表示.在这篇注记中，我们给出了一个反例，然后证明了一个更强的定理，由此Rivest定理得到推论.
In his article “Learning Decision Lists,” Rivest proves that (k-DNF ∪ k-CNF) is a proper subset of k-DL. The proof is based on the following incorrect claim:... if a function f has a prime implicant of size t, then f has no k-DNF representation if k < t.In this note, we show a counterexample to the claim and then prove a stronger theorem, from which Rivest's theorem follows as a corollary.