The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Saturation means to compute the closure of a given set of formulas under a given set of inference rules. Resolution, Knuth/Bendix completion, and Superposition are major examples of saturation-based, automated theorem proving methods. More recently, considerable progress has made in this area. New theoretical insight has been gained. In particular the nature of redundancy and of mechanisms for avoiding...
We use the general scheme of building resolution calculi (also called the inverse method) originating from S.Maslov and G.Mints to design and implement a resolution theorem prover for intuitionistic logic. A number of search strategies are introduced and proved complete. The resolution method is shown to be a decision procedure for a new syntactically described decidable class of intuitionistic logic...
We exploit a system of realizers for classical logic, and a translation from resolution into the sequent calculus, to assess the intuitionistic force of classical resolution for a fragment of intuitionistic logic. This approach is in contrast to formulating locally intuitionistically sound resolution rules. The techniques use the λμε-calculus, a development of Parigot's λμ-calculus.
We characterize provability in intuitionistic logic with equality in terms of a constraint calculus. This characterization uncovers close connections between provability in intuitionistic logic with equality and solutions to simultaneous rigid E-unification. We show that the problem of existence of a sequent proof with a given skeleton is polynomial-time equivalent to simultaneous rigid E-unifiability...
In earlier papers a critic for automatically generalizing conjectures in the context of failed inductive proofs was presented. The critic exploits the partial success of the search control heuristic known as rippling. Through empirical testing a natural generalization and extension of the basic critic emerged. Here we describe our extended generalization critic together with some promising experimental...
We present two learning inference control heuristics for equational deduction. Based on data about facts that contributed to previous proofs, evaluation functions learn to select equations that are likely to be of use in new situations. The first evaluation function works by symbolic retrieval of generalized patterns from a knowledge base, the second function compiles the knowledge into abstract term...
A method is proposed which allows to abduce the definition of a predicate G during the proof attempt of a (faulty) conjecture H(x) such that ∀ x. G(x) → H(x) holds by construction. It is demonstrated how the synthesized predicate may help to complete an induction proof if the faulty conjecture has been obtained as an (over-) generalization of a true conjecture H'(x). An equivalence preserving transformation...
Internal analogy tries to reuse solutions of subproblems within the same problem solving process. In mathematical theorem proving several patterns are known where internal analogy suggests itself. Hence, we propose the use of internal analogy in automated theorem proving. This paper investigates the possibility of incorporating internal analogy into the inductive proof planner CL...
We investigate the improvement of theorem provers by reusing previously computed proofs. We formulate our method for reusing proofs as an instance of the problem reduction paradigm and then develop a termination requirement for our reuse procedure. We prove the soundness of our proposal and show that reusability of proofs is not spoiled by the termination requirement imposed on the reuse procedure...
Termination proofs for recursively defined operations serve several purposes: On the one hand, of course, they ensure the termination of the respective algorithms which is an essential topic in software verification. On the other hand, a successful termination proof allows to use the termination ordering as an induction ordering for future inductive proofs. So far, in the area of explicit inductive...
Running a competition for Automated Theorem Proving (ATP) systems is a difficult and arguable venture. However, the potential benefits of such an event by far outweigh the controversial aspects. The motivations for running the CADE-13 ATP system competition are to contribute to the evaluation of ATP systems, to stimulate ATP research and system development, and to expose ATP systems to interested...
Some higher-order formulas are equivalent to formulas of first-order predicate logic or even propositional logic. In applications where formulas of higherorder predicate logic occur naturally it is very useful to determine whether the given formula is in fact equivalent to a simpler formula of first-order or prepositional logic. Typical applications where this occurs are predicate minimization by...
We examine a problem in formal metatheory: if theories are structured hierarchically, there are metatheorems which hold in only some extensions. We illustrate this using modal logics and the deduction theorem. We show how statements of metatheorems in such hierarchies can take account of possible theory extensions; i.e. a metatheorem formalizes not only the theory in which it holds, but also under...
This paper describes a semantical embedding of the relation based language Ruby in Zermelo-Fraenkel set theory (ZF) using the Isabelle theorem prover. A small subset of Ruby, called Pure Ruby, is embedded as a conservative extension of ZF and many useful structures used in connection with VLSI design are defined in terms of Pure Ruby. The inductive package of Isabelle is used to characterise the Pure...
The verification of programs that contain mutually recursive procedures is a difficult task, and one which has not been satisfactorily addressed in the literature. Published proof rules have been later discovered to be unsound. Verification Condition Generator (VCG) tools have been effective in partially automating the verification of programs, but in the past these VCG tools have in general not themselves...
The FasTraC system provides all facilities to design and validate a decentralized traffic control system for a urban network. Each signal is controlled by an independent control unit. The behavior of the control units is formulated in propositional logic using the quasi-English language of the Leibniz System for logic programming. The latter system compiles these formulations into algorithms that...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.