Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Unification in datastructure multisets
Büttner W. Journal of Automated Reasoning2 (1):75-88,1986.Type:Article
Date Reviewed: Jul 1 1987

An essential part of the resolution method widely used in artificial intelligence (e.g., in Prolog) is unification of terms ti, i.e., finding a substitution s for which s(t1) = S(t- 2). The paper under review is devoted to the unification problem for terms built from variables xi and constants ci by means of an associative and commutative function symbol +. In general, this problem is NP-complete. The author proposes the following approach to this problem. The set of all terms can be embedded into the linear space over Q with base, consisting of xi and ci. In terms of this linear space substitution, s is a linear operation, corresponding to a special type matrix with integral coefficients. This fact reduces the unification problem to the problem of finding integer solutions of linear equations. This reduction leads to a fast parallel algorithm for the case when each of the terms contains variables.

Reviewer:  V. Kreinovich Review #: CR110729
Bookmark and Share
  Featured Reviewer  
 
Resolution (I.2.3 ... )
 
 
Logic Programming (I.2.3 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Resolution": Date
On determining the causes of nonunifiability
Cox P. Journal of Logic Programming 4(1): 33-58, 1987. Type: Article
Jun 1 1988
Completeness results for inequality provers
Bledsoe W., Kunen K., Shostak R. Artificial Intelligence 27(3): 255-288, 1985. Type: Article
Mar 1 1987
First-order logic and automated theorem proving
Fitting M., Gries D., Springer-Verlag New York, Inc., New York, NY, 1990. Type: Book (9780387972336)
Apr 1 1991
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy