基于IMOM和IBOHM启发式策略的扩展规则算法

基于扩展规则的方法是一种定理证明方法.在IER(improved extension rule)扩展规则算法的基础上,提出了IMOM(improved maximum occurrences on clauses of maximum size)和IBOHM(improved BOHM)启发式策略,并将两种启发式策略用于IER算法中,有指导性地选择限定搜索空间的子句,设计并实现了算法IMOMH_IER和IBOHMH_IER.实验结果表明,由于这两种启发式策略能够选择较为合适的搜索空间,可以尽快地判定出原问     

How to avoid the derivation of redundant clauses in reasoning systems

This paper addresses two problems concerning the issue of redundant information in resolution based reasoning systems. The first one deals with the question how the derivation of redundant clauses, such as duplicates or instances of already retained clauses, can be substantially reduced. The second one asks for a criterion to decide, which clauses need not be tested for redundancy. We consider a particular kind of redundancy, which we call ancestor subsumption, that is the subsumption of a resolvent by one of its ancestors. It will be shown that the occurrence of cyclic clause sets, which roughly correspond to sets of logical equivalences, accounts for ancestor subsumed resolvents. Moreover, two techniques will be given to cope with the problems caused by such cyclic structures. The first technique, called literal demodulation, uses logical equivalences as rewrite rules, the second one employs a particular kind of theory resolution.     

Termination of Nested and Mutually Recursive Algorithms

This paper deals with automated termination analysis for functional programs. Previously developed methods for automated termination proofs of functional programs often fail for algorithms with nested recursion and they cannot handle algorithms with mutual recursion.We show that termination proofs for nested and mutually recursive algorithms can be performed without having to prove the correctness of the algorithms simultaneously. Using this result, nested and mutually recursive algorithms do no longer constitute a special problem and the existing methods for automated termination analysis can be extended to nested and mutual recursion in a straightforward way. We give some examples of algorithms whose termination can now be proved automatically (including well-known challenge problems such as McCarthys f_91 function).     

Improving the efficiency of a hyperlinking-based theorem prover by incremental evaluation with network structures

Recently Lee and Plaisted proposed a theorem-proving method, the hyperlinking proof procedure, to eliminate duplication of instances of clauses during the process of inference. A theorem prover, CLIN, which implements the procedure was also constructed. In this implementation, redundant work on literal unification checking, partial unification checking, and duplicate instance checking is performed repetitively, resulting in a large overhead when many rounds of hyperlinking are needed for an input problem. We propose a technique that maintains information across rounds in shared network structures, so that the redundant work in each hyperlinking round can be avoided. Empirical performance comparison has been done between CLIN and CLIN-net, which is the theorem prover with shared network structures, and some results are shown. Problems related to memory overhead and literal ordering are discussed.Supported by National Science Council under grants NSC 81-0408-E-110-509 and NSC-82-0408-E-110-045. A preliminary version of this paper appeared in Proceedings of International Conference on Computing and Information (Sudbury, Ontario Canada, May 1993).     

Efficient Regular Data Structures and Algorithms for Dilation, Location, and Proximity Problems

In this paper we investigate data structures obtained by a recursive partitioning of the multi- dimensional input domain into regions of equal size. One of the best known examples of such a structure is the quadtree . It is used here as a basis for more complex data structures. We also provide multidimensional versions of the stratified tree by van Emde Boas [vEB]. We show that under the assumption that the input points have limited precision (i.e., are drawn from the integer grid of size u ) these data structures yield efficient solutions to many important problems. In particular, they allow us to achieve O(log log u) time per operation for dynamic approximate nearest neighbor (under insertions and deletions) and exact on-line closest pair (under insertions only) in any constant number of dimensions. They allow O(log log u) point location in a given planar shape or in its expansion (dilation by a ball of a given radius). Finally, we provide a linear time (optimal) algorithm for computing the expansion of a shape represented by a region quadtree. This result shows that the spatial order imposed by this regular data structure is sufficient to optimize the operation of dilation by a ball. Received January 19, 1999; revised November 4, 1999.     

Using the VIRT programming language for automatic theorem proving

The expressiveness of the VIRT programming language from the viewpoint of theorem proving is discussed. A program of unit binary resolution is proposed. A comparative analysis of the programming languages VIRT and Lisp is performed. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 87–99, November–December, 1999.     

Gazing: An approach to the problem of definition and lemma use

A major outstanding problem in automated theorem proving research is determining the appropriate use of definitions and previously proved theorems within a proof. Presenting the theorem prover with only the formulae that are necessary for the proof might be viewed as ‘cheating’ and requires that the user prove the theorem ahead of time. In real world applications of theorem proving, this is almost certain to be infeasible. On the other hand providing the prover with all formulae that might be relevant rapidly swamps the prover with unnecessary information. A technique for the selective retrieval of formulae based on features of those formulae and the conjecture at hand is required to solve this problem. In this paper I describe an abstraction-based technique which addresses this problem. Implicit hypotheses such as definitions, axioms and previously proved theorems are stored in a database which may be accessed by a heuristic rule of inference calledgazing. Before accessing this database the gazing rule plans the use of these formulae in a hierarchy of abstraction spaces. When the planning phase is complete, the system can use the indicated formulae with some confidence that they are relevant to the proof. Since the technique is abstraction-based, no guarantee that the plant will be eventually applicable or successful can be made. However, because the plans are built by considering increasing amounts of detail, the number of ways in which the application of a plan can fail is limited. Plan failures may be ‘patched’ in a uniform way.     

Using Resolution for Testing Modal Satisfiability and Building Models

This paper presents a translation-based resolution decision procedure for the multimodal logic K _(m)(,,) defined over families of relations closed under intersection, union, and converse. The relations may satisfy certain additional frame properties. Different from previous resolution decision procedures that are based on ordering refinements, our procedure is based on a selection refinement, the derivations of which correspond to derivations of tableaux or sequent proof systems. This procedure has the advantage that it can be used both as a satisfiability checker and as a model builder. We show that tableaux and sequent-style proof systems can be polynomially simulated with our procedure. Furthermore, the finite model property follows for a number of extended modal logics.     

Computational Semantics in Discourse: Underspecification, Resolution, and Inference

In this paper I introduce a formalism for natural language understandingbased on a computational implementation of Discourse RepresentationTheory. The formalism covers a wide variety of semantic phenomena(including scope and lexical ambiguities, anaphora and presupposition),is computationally attractive, and has a genuine inference component. Itcombines a well-established linguistic formalism (DRT) with advancedtechniques to deal with ambiguity (underspecification), and isinnovative in the use of first-order theorem proving techniques.The architecture of the formalism for natural language understandingthat I advocate consists of three levels of processing:underspecification, resolution, andinference. Each of these levels has a distinct function andtherefore employs a different kind of semantic representation. Themappings between these different representations define the interfacesbetween the levels.I show how underspecified semantic representations can be built in acompositional way (for a fragment of English Grammar) using standardtechniques borrowed from the -calculus, how inferences can becarried out on discourse representations using a translation tofirst-order logic, and how existing research prototypes (discourseprocessing and spoken-dialogue systems) implement the formalism.     

A Disjunctive Positive Refinement of Model Elimination and its Application to Subsumption Deletion

The Model Elimination (ME) calculus is a refutationally complete,goal-oriented calculus for first-order clause logic. In this article, weintroduce a new variant called disjunctive positive ME (DPME); it improveson Plaisteds positive refinement of ME in that reduction steps areallowed only with positive literals stemming from clauses having at leasttwo positive literals (so-called disjunctive clauses). DPME is motivated byits application to various kinds of subsumption deletion: in order to applysubsumption deletion in ME equally successful as in resolution, it iscrucial to employ a version of ME that minimizes ancestor context (i.e., thenecessary A-literals to find a refutation). DPME meets this demand. Wedescribe several variants of ME with subsumption, the most important onesbeing ME with backward and forward subsumption and theT*-Context Check. We compare their pruning power, also takinginto consideration the well-known regularity restriction. All proofs aresupplied. The practicability of our approach is demonstrated with experiments.     

几种提高分布式雷达方位向分辨率方法的分析与比较

分析比较了三种提高分布式合成孔径雷达方位向分辨率的方法:时域扩频,展宽等效多普勒带宽,分辨率虽有提高,但存在频谱混叠,影响成像效果;提高频谱利用率,实现全孔径成像,达到理论分辨率,但多普勒分量提取以及模糊抑制的计算量过大;利用统计分析及估计理论对成像进行空域滤波虽然扩展了清晰成像面积,但没有提高绝对分辨率,且由于矩阵的伪逆操作,计算量惊人。针对上述算法的不足,借鉴扩频思想,提出空间频率滤波方法以改善合成信号的频域特性,从而提高方位向分辨率。给出了仿真结果以说明所提出方法的有效性。     

An integral theorem prover and the role of proof planning

An investigation is made into the ways proof planning can enhance the capability of a rule based prover for the theory of integration. The integrals are of the Riemann type and are defined in a way to maximize the theorem proving methods of predicate calculus. Approximately fifty theorems have been proved and several examples are discussed. A major shortcoming was found to be the inability of the system to work with or produce a proof plan. As a result, a planning scheme based on the idea of subgoals or milestones was considered. With user defined plans, there was a substantial increase in performance and capability of the system and, in some cases, proofs which were previously unsuccessful were completed.     

Extension of some MAP results to transient MAPs and Markovian binary trees

In this work we extend previous results on moment-based characterization and minimal representation of stationary Markovian arrival processes (MAPs) and rational arrival processes (RAPs) to transient Markovian arrival processes (TMAPs) and Markovian binary trees (MBTs).     

An Improvement of Herbrands Theorem and Its Application to Model Generation Theorem Proving

This paper presents an improvement of Herbrand's theorem.We propose a method for specifying a sub- universe of the Herbrand universe of a clause set S for each argument of predicate symbols and function symbols in S. We prove that a clause set S is unsatisfiable if and only if there is a finite unsatisfiable set of ground instances of clauses of S that are derived by only instantiating each variable,which appears as an argument of predicate symbols or function symbols,in S over its corresponding argument's sub-universe of the Herbrand universe of S.Because such sub-universes are usually smaller(sometimes considerably)than the Herbrand universe of S,the number of ground instances may decrease considerably in many cases.We present an algorithm for automatically deriving the sub-universes for arguments in a given clause set,and show the correctness of our improvement.Moreover,we introduce an application of our approach to model generation theorem proving for non-range-restricted problems,show the range-restriction transformation algorithm based on our improvement and provide examples on benchmark problems to demonstrate the power of our approach.     

InequalityProve及一个公开问题的求解

传统的不等式自动证明方法主要依赖于符号计算,一般只能处理代数类型,或可最终转化为代数类型的不等式,而且效率会随着问题中变量个数的增加迅速降低。为克服这些局限性以满足众多实际问题的需要,并充分挖掘计算机在数值计算方面的能力,我们提出以区间分析为工具进行不等式的自动证明。该方法可以处理类型更为一般的不等式,只需对应的函数具有所需的高阶连续可微性质,并且该方法易于实现并行化。本文主要介绍这一方法在Maple系统上的实现,即InequalityProve,并以一个公开问题为例详细说明运用InequalityProve进行不等式证明的一般过程。     

数据结构中二叉树的生成及遍历非递归算法浅析

本文主要介绍数据结构中二叉树的生成,以及二叉树的先序、中序和后序的非递归算法。     

Decision procedures for elementary sublanguages of set theory: X. Multilevel syllogistic extended by the singleton and powerset operators

The class of unquantified formulae of set theory involving Boolean operators, the powerset and singleton operators, and the equality and membership predicates is shown to have a solvable satisfiability problem.It is shown that whenever a formula in the above class is satisfiable there exists a hereditarily finite model of , whose rank is bounded by a doubly exponential expression in the number of variables occurring in .This paper was written while the author was a Visiting Professor at Courant Institute of Mathematical Sciences, New York University, U.S.A.