The Use of Lemmas in the Model Elimination Procedure

When the model elimination (ME) procedure was first proposed, the notion of lemma was put forth as a promising augmentation to the basic complete proof procedure. Here the lemmas that are used are also discovered by the procedure in the same proof run. Several implementations of ME now exist, but only a 1970s implementation explicitly examined this lemma mechanism, with indifferent results. We report on the successful use of lemmas using the METEOR implementation of ME. Not only does the lemma device permit METEOR to obtain proofs not otherwise obtainable by METEOR, or any other ME prover not using lemmas, but some well-known challenge problems are solved. We discuss several of these more difficult problems, including two challenge problems for uniform general-purpose provers, where METEOR was first in obtaining the proof. The problems are not selected simply to show off the lemma device, but rather to understand it better. Thus, we choose problems with widely different characteristics, including one where very few lemmas are created automatically, the opposite of normal behavior. This selection points out the potential of, and the problems with, lemma use. The biggest problem normally is the selection of appropriate lemmas to retain from the large number generated.     

Autarky Pruning in Propositional Model Elimination Reduces Failure Redundancy

Goal-sensitive resolution methods, such as Model Elimination, have been observed to have a higher degree of search redundancy than model-search methods. Therefore, resolution methods have not been seen in high-performance propositional satisfiability testers. A method to reduce search redundancy in goal-sensitive resolution methods is introduced. The idea at the heart of the method is to attempt to construct a refutation and a model simultaneously and incrementally, based on subsearch outcomes. The method exploits the concept of autarky, which can be informally described as a self-sufficient model for some clauses, but which does not affect the remaining clauses of the formula. Incorporating this method into Model Elimination leads to an algorithm called Modoc. Modoc is shown, both analytically and experimentally, to be faster than Model Elimination by an exponential factor. Modoc, unlike Model Elimination, is able to find a model if it fails to find a refutation, essentially by combining autarkies. Unlike the pruning strategies of most refinements of resolution, autarky-related pruning does not prune any successful refutation; it only prunes attempts that ultimately will be unsuccessful; consequently, it will not force the underlying Modoc search to find an unnecessarily long refutation. To prove correctness and other properties, a game characterization of refutation search is introduced, which demonstrates some symmetries in the search for a refutation and the search for a model. Experimental data is presented on a variety of formula classes, comparing Modoc with Model Elimination and model-search algorithms. On random formulas, model-search methods are faster than Modoc, whereas Modoc is faster on structured formulas, including those derived from a circuit-testing application. Considerations for first-order refutation methods are discussed briefly.     

T-Resolution: Refinements and Model Elimination

T-resolution is a binary rule, proposed by Policriti and Schwartz in 1995 for theorem proving in first-order theories (T-theorem proving) that can be seen – at least at the ground level – as a variant of Stickel's theory resolution. In this paper we consider refinements of this rule as well as the model elimination variant of it. After a general discussion concerning our viewpoint on theorem proving in first-order theories and a brief comparison with theory resolution, the power and generality of T-resolution are emphasized by introducing suitable linear and ordered refinements, uniformly and in strict analogy with the standard resolution approach. Then a model elimination variant of T-resolution is introduced and proved to be sound and complete; some experimental results are also reported. In the last part of the paper we present two applications of T-resolution: to constraint logic programming and to modal logic.     

Reasoning Processes in Propositional Logic

We conducted a computer-based psychological experiment in which a random mix of 40 tautologies and 40 non-tautologies were presented to the participants, who were asked to determine which ones of the formulas were tautologies. The participants were eight university students in computer science who had received tuition in propositional logic. The formulas appeared one by one, a time-limit of 45 s applied to each formula and no aids were allowed. For each formula we recorded the proportion of the participants who classified the formula correctly before timeout (accuracy) and the mean response time among those participants (latency). We propose a new proof formalism for modeling propositional reasoning with bounded cognitive resources. It models declarative memory, visual memory, working memory, and procedural memory according to the memory model of Atkinson and Shiffrin and reasoning processes according to the model of Newell and Simon. We also define two particular proof systems, T and NT, for showing propositional formulas to be tautologies and non-tautologies, respectively. The accuracy was found to be higher for non-tautologies than for tautologies (p < .0001). For tautologies the correlation between latency and minimum proof length in T was .89 and for non-tautologies the correlation between latency and minimum proof length in NT was .87.     

Controlled Use of Clausal Lemmas in Connection Tableau Calculi

Proof procedures based on model elimination or the connection tableau calculus have become more and more successful. But these procedures still suffer from long proof lengths as well as from a rather high degree of redundant search effort in comparison with resolution-style search procedures. In order to overcome these problems we investigate the use of clausal lemmas. We develop a method to augment a given set of clauses by a lemma set in a preprocessing phase and discuss the ability of this technique to reduce proof lengths and depths and to provide an appropriate reordering of the search space. We deal with the basic connection tableau calculus as well as with several calculus refinements and extensions. In order to control the use of lemmas we develop techniques for selecting relevant lemmas based on partial evaluation techniques. Experiments with the prover Setheo performed in several domains demonstrate the high potential of our approach.     

基于高斯混合模型的空间域背景分离法及阴影消除法

运动检测和背景分离技术是智能视频监控系统中的一项关键技术。由于目前广泛使用的高斯混合模型背景分离法是在像素域的时间尺度上对像素进行分类,因此常常造成误判,且无法解决阴影问题。为解决此问题,提出了一种空间域上的背景分离法。该方法首先将像素检测从像素域拓展至空间域的局部窗口内;然后在得到前景点集后,再将此空间域检测思想结合像素亮度特征运用到阴影消除中;最后,对经典模型的部分参数估计方法进行了修改。相关的实验结果证明,该方法可用于提高背景分离的检测精度和实现运动物体阴影消除。     

基于极限树特征递归消除和LightGBM的异常检测模型

入侵检测数据维数大、数据样本不均衡、数据集分散性大的问题严重影响分类性能,为了解决该问题,文章提出基于极限随机树的特征递归消除(Extra Trees-Recursive Feature Elimination,ET-RFE)和LightGBM(LGBM)的入侵检测方法。首先对网络数据进行独热编码重构,在数据级层面均衡少量样本的攻击类别;其次,使用基于ET-RFE对流量特征进行降维处理,寻找含有信息量最大的最优特征子集;最后,将得到的最优特征子集作为LGBM输入数据集进行分类训练,并利用贝叶斯算法对LGBM参数进行优化。实验采用真实的网络流量数据集UNSW-NB15,通过与随机森林(RF)、XGboost算法和GALR-DT算法比较可得,文章所提方法能够有效提高检测率,并对小样本攻击类型实现有效的召回率。     

Speaking about Transitive Frames in Propositional Languages

This paper is a comparative study of the propositional intuitionistic (non-modal) and classical modal languages interpreted in the standard way on transitive frames. It shows that, when talking about these frames rather than conventional quasi-orders, the intuitionistic language displays some unusual features: its expressive power becomes weaker than that of the modal language, the induced consequence relation does not have a deduction theorem and is not protoalgebraic. Nevertheless, the paper develops a manageable model theory for this consequence and its extensions which also reveals some unexpected phenomena. The balance between the intuitionistic and modal languages is restored by adding to the former one more implication.     

一种基于统计模型的前景阴影消除算法

视频图像中存在的阴影是影响运动目标检测效果的关键因素之一,对阴影进行检测和消除已成为运动检测中的重要研究内容.针对阴影消除问题,本文采用直方图统计方法,将阴影特征引入到传统混合高斯模型中,基于统计特征建立阴影高斯模型;在模型基础上,提出一种新的前景阴影消除算法,将前景像素与阴影模型进行匹配,实现阴影的判定和消除.与同类算法的对比分析表明:本文算法对于不同场景下的阴影消除是准确且实时的,在阴影检测率和阴影区分度上均有显著提升.     

Conflict-Driven Satisfiability for Theory Combination: Lemmas,Modules, and Proofs

Journal of Automated Reasoning - Search-based satisfiability procedures try to build a model of the input formula by simultaneously proposing candidate models and deriving new formulae implied by...     

Propositional lower bounds: Algorithms and complexity

Propositional greatest lower bounds (GLBs) are logically‐defined approximations of a knowledge base. They were defined in the context of Knowledge Compilation, a technique developed for addressing high computational cost of logical inference. A GLB allows for polynomial‐time complete on‐line reasoning, although soundness is not guaranteed. In this paper we propose new algorithms for the generation of a GLB. Furthermore, we give precise characterization of the computational complexity of the problem of generating such lower bounds, thus addressing in a formal way the question “how many queries are needed to amortize the overhead of compilation?”     

用于仿真的非线性消谐电阻模型建立

在配电网中,谐振回路中串入消谐电阻是抑制或消除谐振的有效措施。在仿真研究谐振过程时,需要消谐电阻的模型。为此提出了一种建立仿真用的消谐电阻模型的方法。方法依据测量的一组电压电流有效值、以及功率序列值,通过递推的方法得到消谐电阻的i-v特性。为了避免v-i特性过零点时的不连续引起仿真模型计算时的参数跃变,造成仿真错误,通过对v-i特性数据扩展、平移预处理,以此数据拟合得到i-v函数,用于消谐电阻的Simulink仿真模型的建立。用仿真验证了方法的正确性和模型的正确性。     

基于DOM持久化的NXD数据存储模型研究

介绍了一个具有专有存储格式和基于DOM持久化技术的NXD数据存储模型。此模型扩展定义了4种持久化DOM节点类型，设计了一种存储混合型XML文档的方法，并依据文档的次序建立了数据聚集。     

Possibilistic Merging and Distance-Based Fusion of Propositional Information

The problem of merging multiple sources information is central in many information processing areas such as databases integrating problems, multiple criteria decision making, expert opinion pooling, etc. Recently, several approaches have been proposed to merge propositional bases, or sets of (non-prioritized) goals. These approaches are in general semantically defined. Like in belief revision, they use implicit priorities, generally based on Dalal's distance, for merging the propositional bases and return a new propositional base as a result. An immediate consequence of the generation of a propositional base is the impossibility of decomposing and iterating the fusion process in a coherent way with respect to priorities since the underlying ordering is lost. This paper presents a general approach for fusing prioritized bases, both semantically and syntactically, when priorities are represented in the possibilistic logic framework. Different classes of merging operators are considered depending on whether the sources are consistent, conflicting, redundant or independent. We show that the approaches which have been recently proposed for merging propositional bases can be embedded in this setting. The result is then a prioritized base, and hence the process can be coherently decomposed and iterated. Moreover, this encoding provides a syntactic counterpart for the fusion of propositional bases.     

Semantics of looping programs in Propositional Dynamic Logic

Standard and nonstandard models of Propositional Dynamic Logic differ in their interpretation of loops. In Standard models, a loop is interpreted as the Kleene closure of the interpretation of its loop body; in nonstandard (Loop Invariant) models, a loop is interpreted as a program which preserves invariant assertions over the loop body.In this paper we show that both interpretations are adequate to represent loops in PDL. We demonstrate this in two ways: First we note that Standard and Loop Invariant models are distinct but not distinguishable within PDL. Second, we show that the class of Loop Invariant models is complete with respect to the Segerberg axiomatization of PDL. Since completeness of the class of Loop Invariant models implies completeness of the class of Standard models, Standard models are also complete with respect to this axiomatization.The research reported here was supported in part by NSF Grants MCS77-02474 and MCS80-05387. Most of the results in this paper were announced in A Completeness Technique forD-axiomatizable Semantics presented at the 11th Annual ACM Symposium on the Theory of Computing in May, 1979.