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

Basic elements of assembly language, Basic elements of  Assembly language:...

Basic elements of  Assembly language: Any Assembly language which consists 3 types of instruction statements that are used to define the program operations: Data secti

What is load-through or early restart, What is load-through or early restar...

What is load-through or early restart? When a read miss happens for a system with cache the needed word may be sent to the processor as soon as it is read from the main memory

Define a segment index or an internal index, The field that contains a segm...

The field that contains a segment index or an internal index is called ? Ans. Target datum consists of a segment index or an internal index.

What is scenarios, Scenarios encapsulate the Vuser Groups and scripts to be...

Scenarios encapsulate the Vuser Groups and scripts to be implemented on load generators at run-time. Manual scenarios can deal out the total number of Vusers between scripts bas

Id3 algorithm - artificial intelligence, Th e ID3 algorithm The cal...

Th e ID3 algorithm The calculation for information gain is the very difficult phase of this algorithm. ID3 performs a search whereby the search states are decision trees an

Explain the term- macro, Explain the term- macro? A term macro is a set...

Explain the term- macro? A term macro is a set of instructions, which can be executed repeatedly. It is useful for automating certain routine tasks like printing reports etc. T

Does c have circular shift operators, No C don't have circular shift operat...

No C don't have circular shift operator. (Part of the reason why that is the sizes of C's types aren't precisely described----but a circular shift makes most sense when applied to

What is wap, What is WAP? WAP is stands for Wireless Application Proto...

What is WAP? WAP is stands for Wireless Application Protocol. It is a global, open standard which gives mobile users access to Internet services by handled devices. Wireless A

Explain the hamiltonian path, What is Hamiltonian path?  A Hamiltonian ...

What is Hamiltonian path?  A Hamiltonian path in a directed graph G is a directed path that goes by each node exactly once. We consider a special case of this difficulty where

Define the pulse-triggered (master-slave) flip-flops, Define the Pulse-Trig...

Define the Pulse-Triggered (Master-Slave) Flip-flops? The term pulse-triggered signify that data are entered into the flip-flop on the rising edge of the clock pulse, though th

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