Equivalent logic programs and symmetric homogeneous forms of logic programs with equality

This article introduces the notion of CAS-equivalent logic programs: logic programs with identical correct answer substitutions. It is shown that the notions CAS-equivalence, refutational equivalence, and logical equivalence do not coincide in the case of definite clause logic programs. Least model criteria for refutational and CAS-equivalence are suggested and their correctness is proved. The least model approach is illustrated by two proofs of CAS-equivalence. It is shown that the symmetric extension of a logic program subsumes the symmetry axiom and the symmetric homogeneous form of a logic program with equality subsumes the symmetry, transitivity, and predicate substitutivity axioms of equality. These results contribute towards the goal of building equality into standard Prolog without introducing additional inference rules.     

Behavioural theories and the proof of behavioural properties

Behavioural theories are a generalization of first-order theories where the equality predicate symbol is interpreted by a behavioural equality of objects (and not by their identity). In this paper we first consider arbitrary behavioural equalities determined by (partial) congruence relations and we show how to reduce the behavioural theory of any class of algebras to (a subset of) the standard theory of some corresponding class of algebras. This reduction is the basis of a method for proving behavioural theorems whenever an axiomatization of the behavioural equality is provided. Then we focus on the important special case of (partial) observational equalities where two elements are observationally equal if they cannot be distinguished by observable computations over some set of input values. We provide general conditions under which an obvious infinite axiomatization of the observational equality can be replaced by a finitary one and we provide methodological guidelines for finding such finitary axiomatizations. As a consequence, any proof system for first-order logic can be used to prove the behavioural validity of first-order formulas with respect to a given (partial) observational equality.     

Adding equality to semantic tableaux

An extension to the system of semantic tableaux to deal with first-order logic with equality is introduced and proved sound and complete. This involves the use of partial unification, an operation which is based on unification without the presence of variables. We show, further, that semantic tableaux with partial unification provide a sound and complete proof method without needing the functionally reflexive axioms. We also give an example of an ordering rule which allows us to provide less complex proofs in the ground case.     

On combinations of propositional dynamic logic and doxastic modal logics

We prove completeness and decidability results for a family of combinations of propositional dynamic logic and unimodal doxastic logics in which the modalities may interact. The kind of interactions we consider include three forms of commuting axioms, namely, axioms similar to the axiom of perfect recall and the axiom of no learning from temporal logic, and a Church–Rosser axiom. We investigate the influence of the substitution rule on the properties of these logics and propose a new semantics for the test operator to avoid unwanted side effects caused by the interaction of the classic test operator with the extra interaction axioms. This paper is a revised and extended version of Schmidt and Tishkovsky (2003).     

Completeness and Counter-Example Generations of a Basic Protocol Logic: (Extended Abstract)

We give an axiomatic system in first-order predicate logic with equality for proving security protocols correct. Our axioms and inference rules derive the basic inference rules, which are explicitly or implicitly used in the literature of protocol logics, hence we call our axiomatic system Basic Protocol Logic (or BPL, for short). We give a formal semantics for BPL, and show the completeness theorem such that for any given query (which represents a correctness property) the query is provable iff it is true for any model. Moreover, as a corollary of our completeness proof, the decidability of provability in BPL holds for any given query. In our formal semantics we consider a “trace” any kind of sequence of primitive actions, counter-models (which are generated from an unprovable query) cannot be immediately regarded as realizable traces (i.e., attacked processes on the protocol in question). However, with the aid of Comon-Treinen's algorithm for the intruder deduction problem, we can determine whether there exists a realizable trace among formal counter-models, if any, generated by the proof-search method (used in our completeness proof). We also demonstrate that our method is useful for both proof construction and flaw analysis by using a simple example.     

A framework for testing first-order logic axioms in program verification

Program verification systems based on automated theorem provers rely on user-provided axioms in order to verify domain-specific properties of code. However, formulating axioms correctly (that is, formalizing properties of an intended mathematical interpretation) is non-trivial in practice, and avoiding or even detecting unsoundness can sometimes be difficult to achieve. Moreover, speculating soundness of axioms based on the output of the provers themselves is not easy since they do not typically give counterexamples. We adopt the idea of model-based testing to aid axiom authors in discovering errors in axiomatizations. To test the validity of axioms, users define a computational model of the axiomatized logic by giving interpretations to the function symbols and constants in a simple declarative programming language. We have developed an axiom testing framework that helps automate model definition and test generation using off-the-shelf tools for meta-programming, property-based random testing, and constraint solving. We have experimented with our tool to test the axioms used in Auto-Cert, a program verification system that has been applied to verify aerospace flight code using a first-order axiomatization of navigational concepts, and were able to find counterexamples for a number of axioms.     

一阶谓词公式关联矩阵的构造方法

一阶谓词逻辑可以借助关联矩阵进行有效推理。为了提高关联矩阵的构造效率,从而提高一阶谓词逻辑推理的效率,提出一种由一阶谓词公式构造对应关联矩阵的递归方法。该方法利用二叉树的递归性质,对任意一个一阶谓词公式,在化去量词后直接构造关联矩阵。该方法为借助关联矩阵实现一阶谓词逻辑的自动化推理提供了可能。     

The consistency of syntactical treatments of knowledge1 (How to compile quantificational modal logics into classical FOL)

The relative expressive power of a sentential operator □α is compared to that of a syntactical predicate L(‘α’) in the setting of first-order logics. Despite well-known results by Montague and by Thomason that claim otherwise, any of the so-called “modal” logics of knowledge and belief can be compiled into classical first-order logics that have a corresponding predicate on sentences. Moreover, through the use of a partial truth predicate, the standard modal axiom schemata can be translated into single sentences, making it possible to use conventional first-order logic theorem provers to directly derive results in a wide class of modal logics.     

Complexity,convexity and combinations of theories

We restrict our attention to decidable quantifier-free theories, such as the quantifier-free theory of integers under addition, the quantifier-free theory of arrays under storing and selecting, or the quantifier-free theory of list structure under cons, car and cdr. We consider combinations of such theories: theories whose sets of symbols are the union of the sets of the symbols of the individual theories and whose set of axioms is the union of the sets of axioms of the individual theories. We give a general technique for determining the complexity of decidable combinations of theories, and show, for example, that the satisfiability problem for the quantifier-free theory of integers, arrays, list structure and uninterpreted function symbols under +, ≤, store, select, cons, car and cdr is NP-complete. We next consider the complexity of the satisfiability problem for formulas already in disjunctive normal form: why some combinations of theories admit deterministic polynomial time decision procedures while for others the problem is NP-hard. Our analysis hinges on the question of whether the theories being combined are convex; that is, whether any conjunction of literals in the theory can entail a proper disjunction of equalities between variables. This leads to a discussion of the role that case analysis plays in deciding combinations of theories.     

Axiom selection over large theory based on new first-order formula metrics

Axiom selection is a task that selects the most likely useful axioms from a large-scale axiom set for proving a given conjecture. Existing axiom selection methods either solely take shallow symbols into account or strongly dependent on previous successful proofs from homologous problems. To address these problems, we introduce a new metric to evaluate the dissimilarity between formulae and utilize it as an evaluator in the selection task. Firstly, we propose a substitution-based metric to compute the dissimilarity between terms. It is a pseudo-metric and can capture the in-depth syntactic difference trigged by both functional and variable subterms. We then extend it to atoms and prove the atom metric also to be a pseudo-metric. Treating formulae as atom sets, we define three kinds of dissimilarity metrics between formulae. Finally, we design and implement conjecture-oriented axiom selection methods based on newly proposed formula metrics. The experimental evaluation is conducted on the MPTP2078 benchmark and demonstrates dissimilarity-based axiom selection improves E prover’s performance. In the best case, it increases the ratio of successful proofs from 30.90% to 42.25%.

     

Data refinement of mixed specifications

Using predicate transformers as a basis, we give semantics and refinement rules for mixed specifications that allow UNITY style specifications to be written as a combination of abstract program and temporal properties. From the point of view of the programmer, mixed specifications may be considered a generalization of the UNITY specification notation to allow safety properties to be specified by abstract programs in addition to temporal properties. Alternatively, mixed specifications may be viewed as a generalization of the UNITY programming notation to allow arbitrary safety and progress properties in a generalized ‘always section’. The UNITY substitution axiom is handled in a novel way by replacing it with a refinement rule. The predicate transformers foundation allows known techniques for algorithmic and data-refinement for weakest precondition based programming to be applied to both safety and progress properties. In this paper, we define the predicate transformer based specifications, specialize the refinement techniques to them, demonstrate soundness, and illustrate the approach with a substantial example. Received: 1 April 1996 / 6 March 1997     

Property persistence in the situation calculus

We develop a new automated reasoning technique for the situation calculus that can handle a class of queries containing universal quantification over situation terms. Although such queries arise naturally in many important reasoning tasks, they are difficult to automate in the situation calculus due to the presence of a second-order induction axiom. We show how to reduce queries about property persistence, a common type of universally-quantified query, to an equivalent form that does not quantify over situations and so is amenable to existing reasoning techniques. Our algorithm replaces induction with a meta-level fixpoint calculation; crucially, this calculation uses only first-order reasoning with a limited set of axioms. The result is a powerful new tool for verifying sophisticated domain properties in the situation calculus.     

Partial ordering in L-underdeterminate sets

The purpose of this paper is to improve results on fuzzy partial orderings obtained by Zadeh in [9]. We overcome the difficulties connected with the axioms of antisymmetry and linearity. Moreover, if the underlying lattice L is a complete residuated lattice, we establish a Szpilrajn theorem, i.e., any (L-fuzzy) partial ordering has a linear extension. In opposition to Zadeh's, our point of view is that an axiom of antisymmetry without a reference to a concept of equality is meaningless. Therefore we first introduce the category LUS (cf. [2]), which can be considered as a mathematical model of fuzzy equality, and subsequently we specify the axioms of (L-fuzzy) partial orderings with respect to the frame given by LUS. The axioms we use clearly display the usefulness of having a Zadeh-like complementation and, as a consequence, the usefulness of a positivistic (and nonintuitionistic) frame of study. An example concerning L°(Rⁿ) which we give clearly shows that the LUS version of the Szpilrajn theorem cannot be reduced to a fuzzification of an already existing theorem, but provides us with additional information.     

Program testing by specification mutation

Both theoretical and empirical arguments suggest that specifications and implementations are equally important sources of information for generating test cases. Nevertheless, the majority of test generation procedures described in the literature deal only with the program source, ignoring specifications. In this paper we outline a procedure for measuring test case effectiveness using specifications given in predicate calculus form. This method is similar to the mutation analysis method of testing programs.     

Predicate abstractions in higher-order logic programming

Lambda calculus offers a natural representation of syntactic structures involving higher-order constructs and local variables, and supports flexible manipulation of such concepts. Thus an integration of logic programming with λ-terms would provide more direct support for metaprogramming. While it is conceptually straightforward to replace first-order terms with λ-terms, the extra search space in unification with respect to λ-conversions cannot be ignored from a practical point of view. Our objective is to explore useful alternatives with weaker conversions that are computationally more tractable. In this paper, we study predicate abstractions, in which λ-abstractions are used to provide anonymous predicates and functions that return predicates. The frameworks is based upon a simple logic of (untyped) λ-calculus, calledL _a .L _a has a general model-theoretic semantics and an equality theory that corresponds to α-equivalence. Intended meanings of predicate abstractions are formalized by equivalence axioms over atomic formulas. We show that under certain conditions, computing with predicate abstractions does not incur any extra search space. Furthermore, programs in this language can be compiled statically into efficient Prolog programs and all most general answers are still preserved.     

Multi-Agent Systems Specification and Certification: A Situation and State Calculus Approach

We address the topic of specifying multi-agent systems using the situation and state calculus (SSC). SSC has been proposed as an extension of the situation calculus to overcome some limitations of the usual notion of state. The envisaged multi-agent system specification framework allows the uniform treatment of both local and global properties, providing also techniques for reasoning about such specifications. When a certain intended property is not inferred from a specification, we cannot always just add to it the corresponding formula. Indeed, it is often the case that specification axioms are required to be formulae of a certain kind. The task of identifying the new axioms that should be added to the specification in order to ensure the intended property has an abductive nature. Herein, we develop abductive reasoning techniques to tackle this problem.     

A Framework for Operational Equational Specifications with Pre-defined Structures

We present a general framework for studying equational specifications with pre-defined structures. The axioms of the specifications are to define new structures in addition to the given ones. In particular, they may define a new operator only partially over some given domain. Our approach allows one to assign easily semantics to such specifications in a denotational and operational fashion. In order to enable functional-style computations, we introduce a semantically enriched notion of term rewriting. This rewrite relation also allows us to infer the consistency of the specification. For the latter purpose one has to show confluence modulo the given structures. We outline how to obtain criteria easily for confluence and termination of the rewrite relation of discourse by generalizing results of the classical syntactic rewrite theory.     

Generalizing DPLL and satisfiability for equalities

We present GDPLL, a generalization of the DPLL procedure. It solves the satisfiability problem for decidable fragments of quantifier-free first-order logic. Sufficient conditions are identified for proving soundness, termination and completeness of GDPLL. We show how the original DPLL procedure is an instance. Subsequently the GDPLL instances for equality logic, and the logic of equality over infinite ground term algebras are presented. Based on this, we implemented a decision procedure for inductive datatypes. We provide some new benchmarks, in order to compare variants.     

Combining Non-Stably Infinite Theories

The Nelson-Oppen combination method combines decision procedures for first-order theories over disjoint signatures into a single decision procedure for the union theory. To be correct, the method requires that the component theories be stably infinite. This restriction makes the method inapplicable to many interesting theories such as, for instance, theories having only finite models.In this paper we provide a new combination method that can combine any theory that is not stably infinite with another theory, provided that the latter is what we call a shiny theory. Examples of shiny theories include the theory of equality, the theory of partial orders, and the theory of total orders.An interesting consequence of our results is that any decision procedure for the satisfiability of quantifier-free Σ-formulae in a Σ-theory T can always be extended to accept inputs over an arbitrary signature Ω Σ.