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

Is the data bus is bi-directional, The data bus is Bi-directional because t...

The data bus is Bi-directional because the similar bus is used for transfer of data among Micro Processor and memory or input / output devices in both the direction.

Vector-vector instructions-vector processing, Vector-Vector Instructions ...

Vector-Vector Instructions In this type, vector operands are fetched by the vector register and saved in another vector register. These instructions are indicated with the foll

How is a multidimensional array defined pointer, How is a multidimensional ...

How is a multidimensional array defined in terms of a pointer to a collection of contiguous arrays of lower dimensionality ? C does not have true multidimensional arrays. Howev

What is the function of cu, What is the function of CU? The control uni...

What is the function of CU? The control unit works as the nerve center that coordinates all the computer operations. It issues timing signals that governs the data transfer.

Illustrate working of t flip-flop, Q. Illustrate working of T Flip-Flop? ...

Q. Illustrate working of T Flip-Flop? T (Toggle) flip-flop is attained from JK flip-flop by combining inputs J and K together. The implementation of T flip-flop is displayed in

IT-Infrasrtucture, Blue Sky events is an organisation that devices and runs...

Blue Sky events is an organisation that devices and runs large outdoor events. They have been commissioned to organise and run an event for four months over the summer period in a

Explain about the voice recognition device, Explain about the Voice recogni...

Explain about the Voice recognition device Blind and partially-sighted people can communicate with a computer using microphone and software (keyboard and touch screens can't be

Determine the objectives of object oriented analysis, Objectives of object ...

Objectives of object oriented analysis After going through this unit, you should be able to: define the concepts of the objects in the system; express desired syste

Explain signed binary number system, Explain signed binary number system. ...

Explain signed binary number system. Ans. Signed Binary Numbers: In decimal number system positive numbers are signified by (+) sign and negative numbers are represented b

Explain that datagram cannot be larger than mtu of a network, "A datagram c...

"A datagram cannot be larger than the MTU of a network over which it is sent." Is the statement true or false? Explain with the help of a suitable example. All hardware technol

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