There have been active work to extend the Prolog style Horn Clause logic programming to non-Horn *** this paper,we will analyze the complexities of several such *** purpose is to understand the computational complexit...
详细信息
There have been active work to extend the Prolog style Horn Clause logic programming to non-Horn *** this paper,we will analyze the complexities of several such *** purpose is to understand the computational complexity of these inference *** analyses do not prove that any one system is better than the others all the *** they do suggest that one system may be better than the others for some particular *** also discuss the effect of caching.
We show that elementary ACI10 unification is in P, even with constant restrictions. As a corollary, we prove that validity of quantified Horn formulae can be tested in O(n2) time. Solvability of elementary disunificat...
We show that elementary ACI10 unification is in P, even with constant restrictions. As a corollary, we prove that validity of quantified Horn formulae can be tested in O(n2) time. Solvability of elementary disunification problems modulo ACI10 is shown to be NP-hard.
Books on software engineering methodologies talk about the significance and need for designing consistent and complete specifications during the requirement analysis and design stages of a software development cycle. ...
详细信息
Theoretical results for identifying unnecessary inferences are discussed in the context of the use of a completion-procedure-based approach toward automated reasoning. The notion of a general superposition is introduc...
Theoretical results for identifying unnecessary inferences are discussed in the context of the use of a completion-procedure-based approach toward automated reasoning. The notion of a general superposition is introduced and it is proved that in a completion procedure, once a general superposition is considered, all its instances are unnecessary inferences and, thus, do not have to be considered. It is also shown that this result can be combined with another criterion, called the prime superposition criterion, proposed by Kapur, Musser, and Narendran, thus implying that prime and general superpositions are sufficient. These results should be applicable to other approaches toward automated reasoning, too. These criteria can be effectively implemented, and their implementation has resulted in automatically proving instances of Jacobson's theorem (also known as the ring commutativity problems) usingRRL (Rewrite Rule Laboratory), a theorem prover based on rewriting techniques and completion.
We analyze the search space of two clause-based proof procedures, the Model Elimination procedure and Near-Horn Prolog, both of Loveland. We study how the search space changes with respect to the degree of how “non-H...
详细信息
The unification problem for terms containing associative and commutative functions is of importance in theorem provers based on term rewriting and resolution methods as well as in logic programming. The complexity of ...
详细信息
Three different methods for automated geometry theorem proving-a generalized version of Dixon resultants, Gröbner bases and characteristic sets--axe reviewed. The main focus is, however, on the use of the general...
详细信息
The concept of anti-link is defined, and useful equivalence-preserving operations on propositional formulas based on anti-links are introduced. These operations eliminate a potentially large number of subsumed paths i...
详细信息
Dixon's method for computing multivariate resultants by simultaneously eliminating many variables is reviewed. The method is found to be quite restrictive because often the Dixon matrix is singular, and the Dixon ...
详细信息
ISBN:
(纸本)9780897916387
Dixon's method for computing multivariate resultants by simultaneously eliminating many variables is reviewed. The method is found to be quite restrictive because often the Dixon matrix is singular, and the Dixon resultant vanished identically yielding no information about solutions for many algebraic and geometry problems. We extend Dixon's method for the case when the Dixon matrix is singular, but satisfies a condition. An efficient algorithm is developed based on the proposed extension for extracting conditions for the existence of affine solutions of a finite set of polynomials. Using this algorithm, numerous geometric and algebraic identities are derived for examples which appear intractable with other techniques of triangulation such as the successive resultant method, the Gro¨bner basis method, Macaulay resultants and Characteristic set method. Experimental results suggest that the resultant of a set of polynomials which are symmetric in the variables is relatively easier to compute using the extended Dixon's method.
暂无评论