自动定理证明：十年回顾

本文主要介绍近十年来定理证明器的发展情况,同时讨论了与自动定理证明相关的一些问题。     

An Algebraic Characterization of Inductive Soundness in Proof by Consistency

Kapur and Musser studied the theoretical basis for proof by consistency and obtained an inductive completeness result:p=q if and only if p=q is true in every inductive model.However,there is a loophole in their proof for the soundness part:p=q implies p=q is true in every inductive model.The aim of this paper is to give a correct characterization of inductive soundness from an algebraic view by introducing strong inductive models.     

I／O归来：Google连接一切

6月,WWDC2014与Google I／O相继召开,这是我第三年参加GoogleI／O大会。每年I／O大会上Google都会展示其最新的产品和技术,本届Google I／O大会,Google向世界展示了一幅场景：Google正在连接一切。     

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.     

改进的双方密钥协商协议

双方认证密钥协商是生成会话密钥的重要手段。分析了赵建杰等于2011年提出的一个可证明安全的双方认证密钥协商协议,指出如果敌手持有原协议的长期私钥,协议是不安全的。提出一种改进的协议,新协议将影响安全性的公开参数保护起来,避免了长期私钥的泄露,并对新协议的安全性和计算量进行了讨论。分析结果表明,新协议在减少计算量的前提下实现了协议双方的安全密钥协商。     

TAPISTRY—A Software Process Improvement Approach Tailored for Small Enterprises

TAPISTRY is a tutored process improvement approach tailored for small enterprises. The approach was developed, used and validated in an ongoing ESSI Esprit project (No 24238), called “TAPISTRY.” The TAPISTRY project adopted a downscaled assessment model of the BOOTSTRAP assessment methodology, called BootCheck, and developed a workshop-based assessment and improvement method, to form together a process improvement approach for small-to-medium-sized enterprises. In TAPISTRY workshops the participants are tutored in self-assessment and improvement planning by software process improvement experts. The resulting TAPISTRY approach was validated through the experiments performed during the TAPISTRY project. This revised version was published online in August 2006 with corrections to the Cover Date.     

<Emphasis Type="Italic">FC</Emphasis>-normal and extended stratified logic program

This paper investigates the consistency property ofFC-normal logic program and presents an equivalent deciding condition whether a logic programP is anFC-normal program. The deciding condition describes the characterizations ofFC-normal program. By the Petri-net presentation of a logic program, the characterizations of stratification ofFC-normal program are investigated. The stratification ofFC-normal program motivates us to introduce a new kind of stratification, extended stratification, over logic program. It is shown that an extended (locally) stratified logic program is anFC-normal program. Thus, an extended (locally) stratified logic program has at least one stable model. Finally, we have presented algorithms about computation of consistency property and a few equivalent deciding methods of the finiteFC-normal program.     

Formal Verification of the <Emphasis Type="Italic">VAMP</Emphasis> Floating Point Unit

We report on the formal verification of the floating point unit used in the VAMP processor. The dual-precision FPU is IEEE compliant and supports denormals and exceptions in hardware. The supported operations are addition, subtraction, multiplication, division, comparison, and conversions.We have formalized the IEEE standard 754. The formalization is supplemented by a rich theory of rounding, which includes notations and theorems facilitating the verification of the actual hardware. The theory of rounding enables the separation of the hardware into smaller modules which can be verified individually. Each module is verified on the gate level against a formal specification. The combination of these formal specifications, together with the theorems from the theory of rounding, yield the overall correctness of the FPU, i.e., theorems stating that the gate-level hardware complies with the high-level formalization of the IEEE standard. The verification is done completely in the theorem prover PVS.We further report on the implementation and test of the verified FPU on a Xilinx FPGA.     

<Emphasis Type="Italic">A</Emphasis>-equilibrium and fuzzy <Emphasis Type="Italic">A</Emphasis>-core in pure exchange model with externalities

The paper suggests the concept of A-equilibrium that is a concretization of the “altruistic” Berge equilibrium adapted to the pure exchange models with externalities. In contrast to the classical markets, these models consider the external influence on the preferences of economic agents. In terms of an appropriate fuzzy domination, a cooperative characterization of the A-equilibrium allocations is given, and an analog of the classic core equivalence theorem is established.     

I-SATCHMO: An Improvement of SATCHMO

We introduce a method for reducing the redundant search space for SATCHMO's model generation approach by means of intelligent backtracking. During the reasoning, we mark an asserted consequent atom as useful whenever it has been used as an antecedent atom for forward chaining. We show that a splitting of the consequence of a non-Horn clause is unnecessary if one of its consequent atoms is found not to be useful at the time it is retracted from the database on backtracking, and therefore the remaining splitting over the clause's consequence can be immediately abandoned. In this way, much of the redundant search space can be eliminated. Our method is simple in principle, easy to implement in Prolog, independent of other refinements, and effective for model generation theorem proving.     

Maximum <Emphasis Type="Italic">k</Emphasis>-Splittable <Emphasis Type="Italic">s</Emphasis>,<Emphasis Type="Italic">t</Emphasis>-Flows

Given a graph with a source and a sink node, the NP-hard maximum k-splittable s,t-flow (M k SF) problem is to find a flow of maximum value from s to t with a flow decomposition using at most k paths. The multicommodity variant of this problem is a natural generalization of disjoint paths and unsplittable flow problems. Constructing a k-splittable flow requires two interdepending decisions. One has to decide on k paths (routing) and on the flow values for the paths (packing). We give efficient algorithms for computing exact and approximate solutions by decoupling the two decisions into a first packing step and a second routing step. Usually the routing is considered before the packing. Our main contributions are as follows: (i) We show that for constant k a polynomial number of packing alternatives containing at least one packing used by an optimal M k SF solution can be constructed in polynomial time. If k is part of the input, we obtain a slightly weaker result. In this case we can guarantee that, for any fixed ε>0, the computed set of alternatives contains a packing used by a (1−ε)-approximate solution. The latter result is based on the observation that (1−ε)-approximate flows only require constantly many different flow values. We believe that this observation is of interest in its own right. (ii) Based on (i), we prove that, for constant k, the M k SF problem can be solved in polynomial time on graphs of bounded treewidth. If k is part of the input, this problem is still NP-hard and we present a polynomial time approximation scheme for it.     

EP<Emphasis Type="Italic">n</Emphasis>P: An Accurate <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis>) Solution to the P<Emphasis Type="Italic">n</Emphasis>P Problem

We propose a non-iterative solution to the PnP problem—the estimation of the pose of a calibrated camera from n 3D-to-2D point correspondences—whose computational complexity grows linearly with n. This is in contrast to state-of-the-art methods that are O(n ⁵) or even O(n ⁸), without being more accurate. Our method is applicable for all n≥4 and handles properly both planar and non-planar configurations. Our central idea is to express the n 3D points as a weighted sum of four virtual control points. The problem then reduces to estimating the coordinates of these control points in the camera referential, which can be done in O(n) time by expressing these coordinates as weighted sum of the eigenvectors of a 12×12 matrix and solving a small constant number of quadratic equations to pick the right weights. Furthermore, if maximal precision is required, the output of the closed-form solution can be used to initialize a Gauss-Newton scheme, which improves accuracy with negligible amount of additional time. The advantages of our method are demonstrated by thorough testing on both synthetic and real-data.     

On Interval Systems [<Emphasis Type="Italic">x</Emphasis>] = [<Emphasis Type="Italic">A</Emphasis>][<Emphasis Type="Italic">x</Emphasis>] + [<Emphasis Type="Italic">b</Emphasis>] and the Powers of Interval Matrices in Complex Interval Arithmetics

For the interval system of equations defined by [x] = [A][x] + [b] we derive necessary and sufficient criteria for the existence of solutions [x]. Furthermore we give necessary and sufficient criteria for the convergence of powers of [A]. In contrast to former results we treat complex interval arithmetics.     

Heidegger on technology and <Emphasis Type="Italic">Gelassenheit</Emphasis>: <Emphasis Type="Italic">wabi</Emphasis>-<Emphasis Type="Italic">sabi</Emphasis> and the art of <Emphasis Type="Italic">Verfallenheit</Emphasis>

The question of the contemporary relevance of Heidegger’s reflections on technology to today’s advanced technology is here explored with reference to the notion of “entanglement” towards a review of Heidegger’s understanding of technology and media, including the entertainment industry and modern digital life. Heidegger’s reflections on Gelassenheit have been connected with the aesthetics of the tea ceremony, disputing the material aesthetics of porcelain versus plastic. Here by approaching the art of wabi-sabi as the art of Verfallenheit, I argue that Gelassenheit may be understood in these terms.     

<Emphasis Type="Italic">LFTOP</Emphasis>: An <Emphasis Type="Italic">LF</Emphasis>-Based Approach to Domain-Specific Reasoning

A new approach to domain-specific reasoning is presented that is based on a type-theoretic logical framework(LF) but does not require the user to be an expert in type theory. The concepts of the domain and its related reasoning systems are formalized in LF, but the user works with the system through a syntax and interface appropriate to his/her work. A middle layer provides translation between the user syntax and LF, and allows additional support for reasoning(e.g., model checking). Thus, the complexity of the logical framework is hidden but the benefits of using type theory and its related tools are retained, such as precision and machine-checkable proofs. This approach is investigated through a number of case studies: here, the authors consider the verification of properties of concurrency. The authors have formalized a specification language (CCS) and logic (μ-calculus) in LF, together with useful lemmas, and a user-oriented syntax has been designed. The authors demonstrate the approach with simple examples. However, applying lemmas to objects introduced by the user may result in framework-level objects which cannot be translated back to the user level. The authors discuss this problem, define a notion of adequacy, and prove that in this case study, translation can always be reversed.     

The constructions for comparing situations with the indices <Emphasis Type="Italic">sort of</Emphasis> and <Emphasis Type="Italic">as if</Emphasis>

The Russian comparative constructions with the word combinations sort of and as if are described with the help of the apparatus of construction grammar that was suggested by Ch. Chilmor. The semantics of these constructions and their syntactic properties that are determined only by semantic differences are analyzed. In particular, it is shown that both constructions must be considered comparative, despite the syntactic differences existing between them. On the other hand, the modal-discursive uses of these constructions that may be of typological interest are analyzed.