The Experts below are selected from a list of 252 Experts worldwide ranked by ideXlab platform
Albert Rubio - One of the best experts on this subject based on the ideXlab platform.
-
Paramodulation with well-founded orderings
2016Co-Authors: Miquel Bofill, Albert RubioAbstract:Abstract For many years, all existing completeness results for Knuth-Bendix completion and ordered Paramodulation required the term order-ing ≻ to be well-founded, monotonic and total(izable) on ground terms. Then, it was shown that well-foundedness and the subterm property were enough for ensuring completeness of ordered Paramodulation. Here we show that the subterm property is not necessary either. By us-ing a new restricted form of rewriting, we obtain a completeness proof of ordered Paramodulation for Horn clauses with equality, where well-foundedness of the ordering suffices. Apart from the theoretical signifi-cance of this result, some potential applications motivating the interest of dropping the subterm property are given. The proof of the results included in this paper, being still technical in some parts, is pretty much shorter and easier to read than the one we have in the preliminary version of this work presented at the CADE 2002 conference [8]. Key words: term rewriting, equational reasoning, theorem proving, Paramodulation, Knuth-Bendix completion
-
Paramodulation with Non-Monotonic Orderings and Simplification
Journal of Automated Reasoning, 2013Co-Authors: Miquel Bofill, Albert RubioAbstract:Ordered Paramodulation and Knuth-Bendix completion are known to remain complete when using non-monotonic orderings. However, these results do not imply the compatibility of the calculus with essential redundancy elimination techniques such as demodulation, i.e., simplification by rewriting, which constitute the primary mode of computation in most successful automated theorem provers. In this paper we present a complete ordered Paramodulation calculus for non-monotonic orderings which is compatible with powerful redundancy notions including demodulation, hence strictly improving the previous results and making the calculus more likely to be used in practice. As a side effect, we obtain a Knuth-Bendix completion procedure compatible with simplification techniques, which can be used for finding, whenever it exists, a convergent term rewrite system for a given set of equations and a (possibly non-totalizable) reduction ordering.
-
Paramodulation with Well-founded Orderings
Journal of Logic and Computation, 2008Co-Authors: Miquel Bofill, Albert RubioAbstract:For many years, all existing completeness results for Knuth–Bendix completion and ordered Paramodulation required the term ordering ≻ to be well-founded, monotonic and total(izable) on ground terms. Then, it was shown that well-foundedness and the subterm property were enough for ensuring completeness of ordered Paramodulation. Here we show that the subterm property is not necessary either. By using a new restricted form of rewriting, we obtain a completeness proof of ordered Paramodulation for Horn clauses with equality, where well-foundedness of the ordering suffices. Apart from the theoretical significance of this result, some potential applications motivating the interest of dropping the subterm property are given. The proof of the results included in this article, being still technical in some parts, is pretty much shorter and easier to read than the one we have in the preliminary version of this work presented at the CADE, 2002 conference (Bofill, and Rubio, 2002, CADE, Vol. 2392 of LNAI, pp. 456–470).
-
redundancy notions for Paramodulation with non monotonic orderings
International Joint Conference on Automated Reasoning, 2004Co-Authors: Miquel Bofill, Albert RubioAbstract:Recently, ordered Paramodulation and Knuth-Bendix completion were shown to remain complete when using non-monotonic orderings. However, these results only implied the compatibility with too weak redundancy notions and, in particular, demodulation could not be applied at all.
-
IJCAR - Redundancy Notions for Paramodulation with Non-monotonic Orderings
Automated Reasoning, 2004Co-Authors: Miquel Bofill, Albert RubioAbstract:Recently, ordered Paramodulation and Knuth-Bendix completion were shown to remain complete when using non-monotonic orderings. However, these results only implied the compatibility with too weak redundancy notions and, in particular, demodulation could not be applied at all.
Miquel Bofill - One of the best experts on this subject based on the ideXlab platform.
-
Paramodulation with well-founded orderings
2016Co-Authors: Miquel Bofill, Albert RubioAbstract:Abstract For many years, all existing completeness results for Knuth-Bendix completion and ordered Paramodulation required the term order-ing ≻ to be well-founded, monotonic and total(izable) on ground terms. Then, it was shown that well-foundedness and the subterm property were enough for ensuring completeness of ordered Paramodulation. Here we show that the subterm property is not necessary either. By us-ing a new restricted form of rewriting, we obtain a completeness proof of ordered Paramodulation for Horn clauses with equality, where well-foundedness of the ordering suffices. Apart from the theoretical signifi-cance of this result, some potential applications motivating the interest of dropping the subterm property are given. The proof of the results included in this paper, being still technical in some parts, is pretty much shorter and easier to read than the one we have in the preliminary version of this work presented at the CADE 2002 conference [8]. Key words: term rewriting, equational reasoning, theorem proving, Paramodulation, Knuth-Bendix completion
-
Paramodulation with Non-Monotonic Orderings and Simplification
Journal of Automated Reasoning, 2013Co-Authors: Miquel Bofill, Albert RubioAbstract:Ordered Paramodulation and Knuth-Bendix completion are known to remain complete when using non-monotonic orderings. However, these results do not imply the compatibility of the calculus with essential redundancy elimination techniques such as demodulation, i.e., simplification by rewriting, which constitute the primary mode of computation in most successful automated theorem provers. In this paper we present a complete ordered Paramodulation calculus for non-monotonic orderings which is compatible with powerful redundancy notions including demodulation, hence strictly improving the previous results and making the calculus more likely to be used in practice. As a side effect, we obtain a Knuth-Bendix completion procedure compatible with simplification techniques, which can be used for finding, whenever it exists, a convergent term rewrite system for a given set of equations and a (possibly non-totalizable) reduction ordering.
-
Paramodulation with Well-founded Orderings
Journal of Logic and Computation, 2008Co-Authors: Miquel Bofill, Albert RubioAbstract:For many years, all existing completeness results for Knuth–Bendix completion and ordered Paramodulation required the term ordering ≻ to be well-founded, monotonic and total(izable) on ground terms. Then, it was shown that well-foundedness and the subterm property were enough for ensuring completeness of ordered Paramodulation. Here we show that the subterm property is not necessary either. By using a new restricted form of rewriting, we obtain a completeness proof of ordered Paramodulation for Horn clauses with equality, where well-foundedness of the ordering suffices. Apart from the theoretical significance of this result, some potential applications motivating the interest of dropping the subterm property are given. The proof of the results included in this article, being still technical in some parts, is pretty much shorter and easier to read than the one we have in the preliminary version of this work presented at the CADE, 2002 conference (Bofill, and Rubio, 2002, CADE, Vol. 2392 of LNAI, pp. 456–470).
-
redundancy notions for Paramodulation with non monotonic orderings
International Joint Conference on Automated Reasoning, 2004Co-Authors: Miquel Bofill, Albert RubioAbstract:Recently, ordered Paramodulation and Knuth-Bendix completion were shown to remain complete when using non-monotonic orderings. However, these results only implied the compatibility with too weak redundancy notions and, in particular, demodulation could not be applied at all.
-
IJCAR - Redundancy Notions for Paramodulation with Non-monotonic Orderings
Automated Reasoning, 2004Co-Authors: Miquel Bofill, Albert RubioAbstract:Recently, ordered Paramodulation and Knuth-Bendix completion were shown to remain complete when using non-monotonic orderings. However, these results only implied the compatibility with too weak redundancy notions and, in particular, demodulation could not be applied at all.
Leo Bachmair - One of the best experts on this subject based on the ideXlab platform.
-
Paramodulation superposition and simplification
Lecture Notes in Computer Science, 1997Co-Authors: Leo BachmairAbstract:Techniques for equational reasoning are a key component in many automated theorem provers and interactive proof and verification systems. A notable recent success in equational theorem proving has been the solution of an open problem (the “Robbins conjecture”) by William McCune with his prover Eqp [13].
-
Basic Paramodulation
Information and Computation, 1995Co-Authors: Leo Bachmair, Harald Ganzinger, Christopher S. Lynch, Wayne SnyderAbstract:AbstractWe introduce a class of restrictions for the ordered Paramodulation and superposition calculi (inspired by the basic strategy for narrowing), which forbid Paramodulation inferences at terms introduced by substitutions from previous inference steps. In addition we introduce restrictions based on term selection rules and redex orderings, which are general criteria for delimiting the terms which are available for inferences. These refinements are compatible with standard ordering restrictions and are complete without Paramodulation into variables or using functional reflexivity axioms. We prove refutational completeness in the context of deletion rules, such as simplification by rewriting (demodulation) and subsumption, and of techniques for eliminating redundant inferences
-
basic Paramodulation and superposition
Conference on Automated Deduction, 1992Co-Authors: Leo Bachmair, Harald Ganzinger, Christopher S. Lynch, Wayne SnyderAbstract:We introduce a class of restrictions for the ordered Paramodulation and superposition calculi (inspired by the basic strategy for narrowing), in which Paramodulation inferences are forbidden at terms introduced by substitutions from previous inference steps. These refinements are compatible with standard ordering restrictions and are complete without Paramodulation into variables or using functional reflexivity axioms. We prove refutational completeness in the context of deletion rules, such as simplification by rewriting (demodulation) and subsumption, and of techniques for eliminating redundant inferences. Finally, we discuss experimental data obtained from a modification of Otter.
-
CADE - Basic Paramodulation and Superposition
Automated Deduction—CADE-11, 1992Co-Authors: Leo Bachmair, Harald Ganzinger, Christopher S. Lynch, Wayne SnyderAbstract:We introduce a class of restrictions for the ordered Paramodulation and superposition calculi (inspired by the basic strategy for narrowing), in which Paramodulation inferences are forbidden at terms introduced by substitutions from previous inference steps. These refinements are compatible with standard ordering restrictions and are complete without Paramodulation into variables or using functional reflexivity axioms. We prove refutational completeness in the context of deletion rules, such as simplification by rewriting (demodulation) and subsumption, and of techniques for eliminating redundant inferences. Finally, we discuss experimental data obtained from a modification of Otter.
-
Kurt Gödel Colloquium - Superposition with Simplification as a Desision Procedure for the Monadic Class with Equality
Lecture Notes in Computer Science, 1Co-Authors: Leo Bachmair, Harald Ganzinger, Uwe WaldmannAbstract:We show that superposition, a restricted form of Paramodulation, can be combined with specifically designed simplification rules such that it becomes a decision procedure for the monadic class with equality. The completeness of the method follows from a general notion of redundancy for clauses and superposition inferences.
Christopher S. Lynch - One of the best experts on this subject based on the ideXlab platform.
-
Paramodulation without duplication
Logic in Computer Science, 1995Co-Authors: Christopher S. LynchAbstract:The resolution (and Paramodulation) inference systems are theorem proving procedures for first-order logic (with equality), but they can run exponentially long for subclasses which have polynomial-time decision procedures, as in the case of SLD resolution and the Knuth-Bendix completion procedure, both in the ground case. Specialized methods run in polynomial time, but have not been extended to the full first-order case. We show a form of Paramodulation which does not copy literals, which runs in polynomial time for the ground case of the following four subclasses: Horn clauses with any selection rule, any set of unit equalities (this includes completion), equational Horn clauses with a certain selection rule, and conditional narrowing.
-
Basic Paramodulation
Information and Computation, 1995Co-Authors: Leo Bachmair, Harald Ganzinger, Christopher S. Lynch, Wayne SnyderAbstract:AbstractWe introduce a class of restrictions for the ordered Paramodulation and superposition calculi (inspired by the basic strategy for narrowing), which forbid Paramodulation inferences at terms introduced by substitutions from previous inference steps. In addition we introduce restrictions based on term selection rules and redex orderings, which are general criteria for delimiting the terms which are available for inferences. These refinements are compatible with standard ordering restrictions and are complete without Paramodulation into variables or using functional reflexivity axioms. We prove refutational completeness in the context of deletion rules, such as simplification by rewriting (demodulation) and subsumption, and of techniques for eliminating redundant inferences
-
Restrictions on Paramodulation
1994Co-Authors: Christopher S. LynchAbstract:In this thesis new restrictions on the Paramodulation inference rule are proposed and shown to be refutation complete when combined with the resolution, factoring and equality resolution inference rules. Evidence is given indicating that this is more efficient than unrestricted Paramodulation. Some of the restrictions proposed are: basic Paramodulation, a restriction on which subterms are paramodulated into; redex orderings, which extend the basic restrictions; and selection rules, which control which literals are allowed to be involved in an inference and further extend the basic restrictions. These restrictions are complete when combined with other known restrictions, such as ordered Paramodulation and superposition, and in the context of deletion strategies such as subsumption, simplification and blocking. The approach to completeness taken in the thesis can also be applied to restrictions on resolution. Completeness of set of support resolution is shown when combined with selection rules and deletion strategies. These general results also provide for the completeness of restricted forms of Knuth-Bendix completion. In that context, constraints encode all known complete restrictions plus some new restrictions developed in this thesis. The basic strategy is directly represented by constraints.
-
basic Paramodulation and superposition
Conference on Automated Deduction, 1992Co-Authors: Leo Bachmair, Harald Ganzinger, Christopher S. Lynch, Wayne SnyderAbstract:We introduce a class of restrictions for the ordered Paramodulation and superposition calculi (inspired by the basic strategy for narrowing), in which Paramodulation inferences are forbidden at terms introduced by substitutions from previous inference steps. These refinements are compatible with standard ordering restrictions and are complete without Paramodulation into variables or using functional reflexivity axioms. We prove refutational completeness in the context of deletion rules, such as simplification by rewriting (demodulation) and subsumption, and of techniques for eliminating redundant inferences. Finally, we discuss experimental data obtained from a modification of Otter.
-
CADE - Basic Paramodulation and Superposition
Automated Deduction—CADE-11, 1992Co-Authors: Leo Bachmair, Harald Ganzinger, Christopher S. Lynch, Wayne SnyderAbstract:We introduce a class of restrictions for the ordered Paramodulation and superposition calculi (inspired by the basic strategy for narrowing), in which Paramodulation inferences are forbidden at terms introduced by substitutions from previous inference steps. These refinements are compatible with standard ordering restrictions and are complete without Paramodulation into variables or using functional reflexivity axioms. We prove refutational completeness in the context of deletion rules, such as simplification by rewriting (demodulation) and subsumption, and of techniques for eliminating redundant inferences. Finally, we discuss experimental data obtained from a modification of Otter.
Yoshiyasu Takefuji - One of the best experts on this subject based on the ideXlab platform.
-
A new perspective of Paramodulation complexity by solving massive 8 puzzles.
arXiv: Computational Complexity, 2020Co-Authors: Ruo Ando, Yoshiyasu TakefujiAbstract:A sliding puzzle is a combination puzzle where a player slide pieces along certain routes on a board to reach a certain end-configuration. In this paper, we propose a novel measurement of complexity of massive sliding puzzles with Paramodulation which is an inference method of automated reasoning. It turned out that by counting the number of clauses yielded with Paramodulation, we can evaluate the difficulty of each puzzle. In experiment, we have generated 100 * 8 puzzles which passed the solvability checking by countering inversions. By doing this, we can distinguish the complexity of 8 puzzles with the number of generated with Paramodulation. For example, board [2,3,6,1,7,8,5,4, hole] is the easiest with score 3008 and board [6,5,8,7,4,3,2,1, hole] is the most difficult with score 48653. Besides, we have succeeded to obverse several layers of complexity (the number of clauses generated) in 100 puzzles. We can conclude that proposal method can provide a new perspective of Paramodulation complexity concerning sliding block puzzles.