Efficient instance retrieval with standard and relational path indexing

Backward demodulation is a simplification technique used in saturation-based theorem proving with superposition and ordered paramodulation. It requires instance retrieval, i.e., search for instances of some term in a typically large set of terms. Path indexing is a family of indexing techniques that can be used to solve this problem efficiently. We propose a number of powerful optimisations to standard path indexing. We also describe a novel framework that combines path indexing with relational joins. The main advantage of the proposed scheme is flexibility, which we illustrate by sketching how to adapt the scheme to instance retrieval modulo commutativity and backward subsumption on multi-literal clauses.     

Similarity,topology, and uniformity

We generalize various notions of generalized metrics even further to one general concept comprising them all. For convenience, we turn around the ordering in the target domain of the generalized metrics so that we speak of similarity instead of distance. Starting from an extremely general situation without axioms, we examine which axioms or additional properties are needed to obtain useful results. For instance, we shall see that commutativity and associativity of the generalized version of addition occurring in the triangle inequality are not really needed, nor do we require a generalized version of subtraction.Each similarity space comes with its own domain of possible similarity values. Therefore, we consider non-expanding functions modulo some rescaling between different domains of similarity values. We show that non-expanding functions with locally varying rescaling functions correspond to topologically continuous functions, while non-expanding functions with a globally fixed rescaling generalize uniformly continuous functions.     

Tractability through symmetries in propositional calculus

Many propositional calculus problems — for example the Ramsey or the pigeon-hole problems — can quite naturally be represented by a small set of first-order logical clauses which becomes a very large set of propositional clauses when we substitute the variables by the constants of the domainD. In many cases the set of clauses contains several symmetries, i.e. the set of clauses remains invariant under certain permutations of variable names. We show how we can shorten the proof of such problems. We first present an algorithm which detects the symmetries and then we explain how the symmetries are introduced and used in the following methods: SLRI, Davis and Putnam and semantic evaluation. Symmetries have been used to obtain results on many known problems, such as the pigeonhole, Schur's lemma, Ramsey's, the eight queen, etc. The most interesting one is that we have been able to prove for the first time the unsatisfiability of Ramsey's problem (17 vertices and three colors) which has been the subject of much research.     

Modular proof systems for partial functions with Evans equality

The paper presents a modular superposition calculus for the combination of first-order theories involving both total and partial functions. The modularity of the calculus is a consequence of the fact that all the inferences are pure—only involving clauses over the alphabet of either one, but not both, of the theories—when refuting goals represented by sets of pure formulae. The calculus is shown to be complete provided that functions that are not in the intersection of the component signatures are declared as partial. This result also means that if the unsatisfiability of a goal modulo the combined theory does not depend on the totality of the functions in the extensions, the inconsistency will be effectively found. Moreover, we consider a constraint superposition calculus for the case of hierarchical theories and show that it has a related modularity property. Finally, we identify cases where the partial models can always be made total so that modular superposition is also complete with respect to the standard (total function) semantics of the theories.     

Regaining cut admissibility in deduction modulo using abstract completion

Deduction modulo is a way to combine computation and deduction in proofs, by applying the inference rules of a deductive system (e.g. natural deduction or sequent calculus) modulo some congruence that we assume here to be presented by a set of rewrite rules. Using deduction modulo is equivalent to proving in a theory corresponding to the rewrite rules, and leads to proofs that are often shorter and more readable. However, cuts may be not admissible anymore.We define a new system, the unfolding sequent calculus, and prove its equivalence with the sequent calculus modulo, especially w.r.t. cut-free proofs. It permits to show that it is even undecidable to know if cuts can be eliminated in the sequent calculus modulo a given rewrite system.Then, to recover the cut admissibility, we propose a procedure to complete the rewrite system such that the sequent calculus modulo the resulting system admits cuts. This is done by generalizing the Knuth–Bendix completion in a non-trivial way, using the framework of abstract canonical systems.These results enlighten the entanglement between computation and deduction, and the power of abstract completion procedures. They also provide an effective way to obtain systems admitting cuts, therefore extending the applicability of deduction modulo in automated theorem proving.     

Implementing the Davis–Putnam Method

The method proposed by Davis, Putnam, Logemann, and Loveland for propositional reasoning, often referred to as the Davis–Putnam method, is one of the major practical methods for the satisfiability (SAT) problem of propositional logic. We show how to implement the Davis–Putnam method efficiently using the trie data structure for propositional clauses. A new technique of indexing only the first and last literals of clauses yields a unit propagation procedure whose complexity is sublinear to the number of occurrences of the variable in the input. We also show that the Davis–Putnam method can work better when unit subsumption is not used. We illustrate the performance of our programs on some quasigroup problems. The efficiency of our programs has enabled us to solve some open quasigroup problems.     

Algorithms for minimization of finite acyclic automata and pattern matching in terms

Two equivalence relations for finite acyclic automata are considered and minimization algorithms for these automata are described. From these algorithms we develop algorithms for deciding identity of terms, matching of subterms, and pattern matching in terms, which allow for commutativity and associativity of operations.Translated from Kibernetika, No. 3, pp. 11–16, May–June, 1991.     

Abstract Congruence Closure

We describe the concept of an abstract congruence closure and provide equational inference rules for its construction. The length of any maximal derivation using these inference rules for constructing an abstract congruence closure is at most quadratic in the input size. The framework is used to describe the logical aspects of some well-known algorithms for congruence closure. It is also used to obtain an efficient implementation of congruence closure. We present experimental results that illustrate the relative differences in performance of the different algorithms. The notion is extended to handle associative and commutative function symbols, thus providing the concept of an associative-commutative congruence closure. Congruence closure (modulo associativity and commutativity) can be used to construct ground convergent rewrite systems corresponding to a set of ground equations (containing AC symbols). This revised version was published online in August 2006 with corrections to the Cover Date.     

Clausal Presentation of Theories in Deduction Modulo

Resolution modulo is an extension of first-order resolution in which rewrite rules are used to rewrite clauses during the search. In the first version of this method, clauses are rewritten to arbitrary propositions. These propositions are needed to be dynamically transformed into clauses. This unpleasant feature can be eliminated when the rewrite system is clausal, i.e., when it rewrites clauses to clauses. We show in this paper how to transform any rewrite system into a clausal one, preserving the existence of cut free proofs of any sequent.     

A systematic security analysis of EMV protocol

EMV is the leading and widely used international standard for payment with smart cards. The EMV specification defines a highly configurable toolkit for payment protocols, which allows different combinations of card authentication, cardholder authentication and transaction authorization. Due to its complexity and its flexibility, it is difficult to comprehensively analyze the security of EMV standard, yet it is critical to obtain practical security guarantees for EMV. In this paper, we present the first systematic and formal treatment of EMV protocol. We introduce a three-party security model, covering all known kinds of combinations and providing reasonably strong security notions. Furthermore, via a modular approach, we prove that the EMV protocol with reasonable improvement can achieve our desired security. We also identify various known attacks on EMV protocol in our security model.     

External Rewriting for Skeptical Proof Assistants

This paper presents the design, the implementation, and experiments of the integration of syntactic, conditional possibly associative-commutative term rewriting into proof assistants based on constructive type theory. Our approach is called external because it consists in performing term rewriting in a specific and efficient environment and checking the computations later in a proof assistant. Two typical systems are considered in this work: ELAN, based on the rewriting calculus, as the term rewriting-based environment, and Coq, based on the calculus of inductive constructions as the proof assistant. We first formalize the proof terms for deduction by rewriting and strategies in ELAN using the rewriting calculus with explicit substitutions. We then show how these proof terms can soundly be translated into Coq syntax where they can be directly type checked. For the method to be applicable for rewriting modulo associativity and commutativity, we provide an effective method to prove equalities modulo these axioms in Coq using ELAN. These results have been integrated into an ELAN-based rewriting tactic in Coq.     

Modular specification of frame properties in JML

We present a modular specification technique for frame properties. The technique uses modifies clauses and abstract fields with declared dependencies. Modularity is guaranteed by a programming model that enforces data abstraction by preventing representation and argument exposure, a semantics of modifies clauses that uses a notion of ‘relevant location’, and by modularity rules for dependencies. For concreteness, we adapt this technique to the Java Modeling Language, JML. Copyright © 2003 John Wiley & Sons, Ltd.     

Toward Non Commutative Numerical Analysis: High Order Integration in Time

We review some methods for high precision time integration: it is not easy to ensure stability, precision and numerical efficiency at the same time. Operator splitting—when it works—can be a good way to satisfy all these constraints; in some cases, the order of the splitting schemes can be enhanced by extrapolation; nevertheless, the applicability of splitting is limited due to non commutativity. As an alternative to splitting, we introduce preconditioned Runge–Kutta (PRK) schemes: the preconditioning is included in the scheme, instead of being put aside for implementation. Examples of PRK schemes are given including the extrapolation of the residual smoothing scheme, and sufficient conditions for stability are described.     

Good reduction of Puiseux series and applications

We have designed a new symbolic-numeric strategy for computing efficiently and accurately floating point Puiseux series defined by a bivariate polynomial over an algebraic number field. In essence, computations modulo a well-chosen prime number p are used to obtain the exact information needed to guide floating point computations. In this paper, we detail the symbolic part of our algorithm. First of all, we study modular reduction of Puiseux series and give a good reduction criterion for ensuring that the information required by the numerical part is preserved. To establish our results, we introduce a simple modification of classical Newton polygons, that we call “generic Newton polygons”, which turns out to be very convenient. Finally, we estimate the size of good primes obtained with deterministic and probabilistic strategies. Some of these results were announced without proof at ISSAC’08.     

优化参数化二元模映射信息隐藏

目的 针对目前信息隐藏的嵌入和提取函数为固定表达式,存在容易被隐写分析和非法提取信息的安全隐患,以及基于模函数的隐写研究现状,提出信息隐藏参数化设计思想、优化参数化二元模映射隐写算法。方法 首先提出信息隐藏参数化设计定义和分析参数化信息隐藏算法的安全性,然后提出优化参数化二元模映射隐写算法。优化参数化二元模映射隐写算法将两个像素值优化组合后的模运算结果映射到一位n²进制信息,从而实现信息隐藏。结果 优化参数化二元模映射隐写算法的密钥空间大,载密图像均方差小于或等于同类算法。结论 信息隐藏参数化设计可以有效提高信息隐藏算法的抗隐写分析能力和抗信息提取能力;优化参数化二元模映射隐写算法与同类算法相比,具有更好的载密图像视觉质量和安全性。     

A Shortest 2-Basis for Boolean Algebra in Terms of the Sheffer Stroke

In this article, we present a short 2-basis for Boolean algebra in terms of the Sheffer stroke and prove that no such 2-basis can be shorter. We also prove that the new 2-basis is unique (for its length) up to applications of commutativity. Our proof of the 2-basis was found by using the method of proof sketches and relied on the use of an automated reasoning program. This revised version was published online in August 2006 with corrections to the Cover Date.     

Alternating two-way AC-tree automata

We explore the notion of alternating two-way tree automata modulo the theory of finitely many associative-commutative (AC) symbols. This was prompted by questions arising in cryptographic protocol verification, in particular in modeling group key agreement schemes based on Diffie-Hellman-like functions, where the emptiness question for intersections of such automata is fundamental. This also has independent interest. We show that the use of general push clauses, or of alternation, leads to undecidability, already in the case of one AC symbol, with only functions of arity zero. On the other hand, emptiness is decidable in the general case of several function symbols, including several AC symbols, provided push clauses are unconditional and intersection clauses are final. This class of automata is also shown to be closed under intersection.     

A security flow control algorithm and its denotational semantics correctness proof

We derive a security flow control algorithm for message-based, modular systems and prove the algorithm correct. The development is noteworthy because it is completely rigorous: the flow control algorithm is derived as an abstract interpretation of the denotational semantics of the programming language for the modular system, and the correctness proof is a proof by logical relations of the congruence between the denotational semantics and its abstract interpretation. Effectiveness is also addressed: we give conditions under which an abstract interpretation can be computed as a traditional iterative data flow analysis, and we prove that our security flow control algorithm satisfies the conditions. We also show that symbolic expressions (that is, data flow values that contain unknowns) can be used in a convergent, iterative analysis. An important consequence of the latter result is that the security flow control algorithm can analyse individual modules in a system for well formedness and later can link the analyses to obtain an analysis of the entire system.