Unification algorithm - artificial intelligence, Computer Engineering

Assignment Help:

Unification Algorithm - Artificial intelligence:

To merge two statements, we should get a substitution which forms the two sentences similar. Remember that we write V/T to signify that we have substituted term T for  variable  V  (read  the  "/"  sign  as  "is  substituted  by").  The purpose  of this algorithm will be to construct a substitution (a set of pairs V/T) for a provided pair of statements. So, for example, the output for the pair of       statements:

Knows (john)

Knows (john, marry)

Will be: {X/mary}. However, for the two sentences on the top involving jack, the method must fail, as there was no method to unify the sentences.

To explain the algorithm, we have to specify some methods it calls internally.

  • The function is a variable(x) checks whether x is a variable.
  • The function is a compound(x) checks if x is a compound expression: else a predicate, a method or a connective which includes subparts. The subparts of a procedure or predicate are the arguments. The subparts of a

Connectives are the things it joins. We write rags(x) for the subparts of complex expression x. Note that args(x) outputs a list: the list of subparts. Also, we write op(x) to signify the symbol of the complex operator (predicate name, method name or connective symbol).

  • The function is a list(x) checks whether x is a list. We write head(L) for the very first term in a list L and tail(L) for the sub list comprising all the another terms besides the top. Hence the top of [2,3,5,7,11] is 2 and the tail is [3,5,7,11]. This terminology is ordinary in Prolog.

It's very easy to clarify the unification algorithm as a recursive way which is capable to call itself. As this is occurring, a set, mu, is passed around the many parts of the algorithm, gathering substitutions as it goes. The method has two basic parts:

Unify internal(x, y, mu)

which returns a substitution which forms sentence x look exactly as sentence y, given an already presented set of substitutions mu (although mu may be empty). This function checks many properties of x and y and calls either itself again or the

unify variable routine,  as  given  below.  Note that the  order  of  the  if- statements is important, and if a breakdown is reported at any stage, the complete function fails. If none of the cases is right for the input, then the algorithm fails to search a unifying set of substitutions.

Unify variable (var, x, mu)

which gets back a substitution provided a variable var, a sentence x and an already present set of substitutions mu. This function also includes a set of cases which results other routines to run if the case is right of the input. Again, the order of the cases is essential. Here, if none of the cases is right of the input, a substitution is got back.

The algorithm is as follows:

unify(x,y) = unify_internal(x,y,{}) unify_internal(x,y,mu) ---------------------- Cases

1. if (mu=failure) then return failure

2. if (x=y) then return mu.

3. if (isa_variable(x)) then return unify_variable(x,y,mu)

4. if (isa_variable(y)) then return unify_variable(y,x,mu)

5. if (isa_compound(x) and isa_compound(y)) then return unify_internal(args(x),args(y),unify_internal(op(x),op(y),mu))

6. if (isa_list(x) and isa_list(y)) then return unify_internal(tail(x),tail(y),unify_internal(head(x),head(y),mu))

7. return failure

unify_variable(var,x,mu) ------------------------ Cases

1. if (a substitution var/val is in mu) then return unify_internal(val,x,mu)

2. if (a substitution x/val is in mu) then return unify_internal(var,val,mu)

3. if (var occurs anywhere in x) then return failure

4. add var/x to mu and return


Related Discussions:- Unification algorithm - artificial intelligence

Show the dynamic range and colour depth, Q. Show the Dynamic Range and Colo...

Q. Show the Dynamic Range and Colour Depth? Dynamic Range is the number of colours a colour scan or number of grays a monochrome scanner can distinguish. The dynamic range is t

What is optical character recognition, What is Optical character recognitio...

What is Optical character recognition (OCR)  Information on paper is automatically read by a scanner and is then processed/analysed by OCR software and stored in an electronic

Vector-scalar instructions- vector processing, Vector-Scalar Instructions :...

Vector-Scalar Instructions : In this type, when the combination of vector and scalar are fetched and saved in vector register. These instructions are denoted with the many function

What is single program multiple data, Q. What is Single Program Multiple Da...

Q. What is Single Program Multiple Data (SPMD) SPMD is in fact a "high level" programming model which can be built on any arrangement of previously described parallel programmi

Concept of pipelining, Describe the concept of pipelining. Ans: Pipeli...

Describe the concept of pipelining. Ans: Pipelining is the means of executing machine instructions concurrently. This is the effective way of organizing concurrent activity in

What are the advantages of public key cryptography, What are the advantages...

What are the advantages of Public Key Cryptography? Advantages of Public Key Cryptography are illustrated in below: a) Increased convenience and security and b) Electro

Complicated question, Hi I need a help in this question : A telephone sw...

Hi I need a help in this question : A telephone switchboard handles ? calls on average during a rush hour, and the switchboard can at most make k connections per minute. Write a

Java, what is java?

what is java?

What are the uses of interrupts, What are the uses of interrupts?  ...

What are the uses of interrupts?  Recovery from errors Debugging Communication among programs Use of interrupts in operating system

Simplify the expression by using karnaugh map, Simplify   the   following  ...

Simplify   the   following   expression   into   sum   of   products   using   Karnaugh   map F(A, B, C, D) = ∑ (1,3,4,5,6,7,9,12,13) Ans. Simplification of the giv

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd