对于析取范式的构造的一个全局性分析

我们考虑具有优先代表资格的NP完全问题——析取范式的永真性判定问题。本文从全局性构造的角度对它作了某种分析,得出如下结果:在由n个确定的命题变元所可能构成的一切析取范式中,永真析取范式的个数与非永真析取范式的个数之比当n趋于无穷时为无穷大。 基于所得结果,对于析取范式永真性判定问题得出了一个近似快速的求解算法,按此算法,对绝大多数的析取范式,其永真性问题,在多项式时间内都可解决。     

用均覆盖和锥形式对析取范式的结构分析及其近似快速求解算法

本文对析取范式的结构作了结构分析，得出了如下结果；在恰当由ｎ个确定的例题变元所可能构成的一切析取范式中，含均覆盖的析取范式的比例当ｎ趋于无穷大时等于１。在其余的析取范式中，含锥形式的比例当ｎ趋于无穷大时亦等于１。基于分析结果，给出一个判定析取范式永真性的快速算地。     

关于求解DNF永真性问题的近似快速算法的研究

本文研究了用吸收关系与补关系构造求解DNF的永真性的近似快速算法问题。在第二节给出了偏序集〈S;≤〉的定义,研究了〈S;≤〉上的链与反链的性质。在第三节巧妙地借助补关系图构造了一个求解DNF的永真性的分治算法。     

有穷客体域中一阶谓词公式的一种自动化判定法

本文给出了一个在自然数的有穷客体域Dk={1,2,…,k}(k≥0) 内一阶谓词逻辑公式的k普遍有效性的判定算法。对于只包含一元谓词的公式以及对于带有前束量词 (m≥0,n≥0)且内部无自由变元的前束范式,该判定算法可判定这些公式的永真性,从而使该判定算法突破了有穷客体域以及k普遍有效性的局限。     

基于Skowron分明矩阵的快速约简算法

属性约简是Rough集理论的核心内容之一,计算所有的属性约简已经被证明是NP完全问题。本文基于分而自治思想,在Skowron分明矩阵法的基础上,给出了最小析取范式的判定定理,从而提出了计算所有属性约简的算法。理论分析和实验结果表明,该约简算法在效率上较现有的算法有显著提高。     

连接不失真性的判断

本文提出判定接不失真性的又一个必要条件，发现了连接不失真的充要条件。文中有关理论补充并推广了文献（１）中的有关理论。     

粗糙集理论中析取范式生成算法

知识约简是粗糙集理论研究的主要内容之一,而析取范式的生成又是知识约简的重点,本文提出的析取范式生成算法可以直接从合取范式生成析取范式,同时给出了属性约简算法的具体步骤,还进行了时间复杂性的分析和实例验证,表明算法的有效性。     

极小子集问题的逻辑代数解法

在粗集论中，决策表简化问题可转化为极小子集问题.本文给出极小子集问题的逻辑代数解法，即通过求逻辑函数的极小析取范式或极小合取范式来获得极小子集.     

从合取范式到析取范式的转换研究

为了解决粗糙集分辨函数的计算、概念格中内涵缩减的计算、逻辑程序设计的规则简化等问题,抽象出了从合取范式到析取范式转换这一核心问题。提出了利用极小覆盖来实现从合取范式到析取范式的转换,给出了一个增量式的算法。为了扩大范式转换的使用范围,定义了伪合取范式,并给出伪合取范式到析取范式的转换方法。     

基于多线程技术的分辨函数析取范式生成算法

基于分辨矩阵计算信息系统的所有约简,都需要将合取范式转化为析取范式,但是该转化过程存在组合爆炸问题。为解决该问题,根据合取范式、合取运算和析取运算的特点,构建析取范式转化的并行模型,提出基于多线程技术的分辨函数析取范式生成算法,利用Windows的自动线程调度功能提高范式转换的效率。实验结果表明,该算法的析取范式转化效率会随着合取范式长度的增加而提高,适合在多核CPU计算机上运行。     

Theory Revision with Queries: DNF Formulas

The theory revision, or concept revision, problem is to correct a given, roughly correct concept. This problem is considered here in the model of learning with equivalence and membership queries. A revision algorithm is considered efficient if the number of queries it makes is polynomial in the revision distance between the initial theory and the target theory, and polylogarithmic in the number of variables and the size of the initial theory. The revision distance is the minimal number of syntactic revision operations, such as the deletion or addition of literals, needed to obtain the target theory from the initial theory. Efficient revision algorithms are given for three classes of disjunctive normal form expressions: monotone k-DNF, monotone m-term DNF and unate two-term DNF. A negative result shows that some monotone DNF formulas are hard to revise.     

On one class of decision diagrams

A class of decision diagrams for representation of the normal forms of Boolean functions was introduced. Consideration was given, in particular, to the disjunctive diagrams representing the disjunctive normal forms (DNF). In distinction to the binary decision diagrams (BDD) and reduced ordered binary decision diagram (ROBDD), the disjunctive diagram representing an arbitrary DNF is constructed in a time which is polynomial of the size of the DNF binary code. Corresponding algorithms were described, and the results were presented of the computer-aided experiments where the proposed diagrams were used to reduce the information content accumulated in the course of deciding hard variants of Boolean satisfiability problem (SAT).     

Finding a short and accurate decision rule in disjunctive normal form by exhaustive search

Greedy approaches suffer from a restricted search space which could lead to suboptimal classifiers in terms of performance and classifier size. This study discusses exhaustive search as an alternative to greedy search for learning short and accurate decision rules. The Exhaustive Procedure for LOgic-Rule Extraction (EXPLORE) algorithm is presented, to induce decision rules in disjunctive normal form (DNF) in a systematic and efficient manner. We propose a method based on subsumption to reduce the number of values considered for instantiation in the literals, by taking into account the relational operator without loss of performance. Furthermore, we describe a branch-and-bound approach that makes optimal use of user-defined performance constraints. To improve the generalizability we use a validation set to determine the optimal length of the DNF rule. The performance and size of the DNF rules induced by EXPLORE are compared to those of eight well-known rule learners. Our results show that an exhaustive approach to rule learning in DNF results in significantly smaller classifiers than those of the other rule learners, while securing comparable or even better performance. Clearly, exhaustive search is computer-intensive and may not always be feasible. Nevertheless, based on this study, we believe that exhaustive search should be considered an alternative for greedy search in many problems.     

Symmetric approximation arguments for monotone lower bounds without sunflowers

We propose a symmetric version of Razborov's method of approximation to prove lower bounds for monotone circuit complexity. Traditionally, only DNF formulas have been used as approximators, whereas we use both CNF and DNF formulas. As a consequence we no longer need the Sun ower Lemma that has been essential for the method of approximation. The new approximation argument corresponds to Haken's recent method for proving lower bounds for monotone circuit complexity (counting bottlenecks) in a natural way.?We provide lower bounds for the BMS problem introduced by Haken, Andreev's polynomial problem, and for Clique. The exponential bounds obtained are the same as those previously best known for the respective problems. Received: July 16, 1996.     

On the capabilities of higher-order neurons: a radial basis function approach

Higher-order neurons with k monomials in n variables are shown to have Vapnik-Chervonenkis (VC) dimension at least nk + 1. This result supersedes the previously known lower bound obtained via k-term monotone disjunctive normal form (DNF) formulas. Moreover, it implies that the VC dimension of higher-order neurons with k monomials is strictly larger than the VC dimension of k-term monotone DNF. The result is achieved by introducing an exponential approach that employs gaussian radial basis function neural networks for obtaining classifications of points in terms of higher-order neurons.     

Boolean functions with long prime implicants

In this short note we introduce a hierarchy of classes of Boolean functions, where each class is defined by the minimum allowed length of prime implicants of the functions in the class. We show that for a given DNF and a given class in the hierarchy, it is possible to test in polynomial time whether the DNF represents a function from the given class. For the first class in the hierarchy we moreover present a polynomial time algorithm which for a given input DNF outputs a shortest logically equivalent DNF, i.e. a shortest DNF representation of the underlying function. This class is therefore a new member of a relatively small family of classes for which the Boolean minimization problem can be solved in polynomial time. For the second class and higher classes in the hierarchy we show that the Boolean minimization problem can be approximated within a constant factor.     

Efficient construction of DNF for some boolean functions with a small number of zeros

Boolean functions with a small number of zeros are studied. A linear algorithm for constructing a dead-end disjunctive normal form (DNF) is obtained for a function of special form from this class. The resulting dead-end DNF insignificantly differs from theoretical estimates for the minimal DNF.