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

Explain about theta notation, Q. Explain about Theta Notation? Theta Θ...

Q. Explain about Theta Notation? Theta Θ Notation : The set Θ (g(n)) comprises all functions f(n) for that there exist positive constants c1,c2 such that f(n) is squeezed in b

Explain the register transfer language, Explain the Register transfer langu...

Explain the Register transfer language Register transfer language means there must be data flow between two registers and logic is in between them for end registers data must f

Overflow or underflow for floating point numbers, In floating point numbers...

In floating point numbers when so you say that an overflow or underflow has occurred? Ans: A) In single precision numbers when an exponent is less than +127 then we say that

Design requirements of sequential circuit, What are the Requirements to des...

What are the Requirements to design Sequential circuit Ans . Design Requirements of Sequential circuit: (i) The circuit specifications translated into a state diagram

Explain vector-memory instructions, Vector-Memory Instructions When vec...

Vector-Memory Instructions When vector operations with memory M are carried out then these are vector-memory instructions. These instructions are referred with the subsequent f

Implementation of arithmetic circuits, Implementation of Arithmetic Circuit...

Implementation of Arithmetic Circuits for Arithmetic Micro-operation  An arithmetic circuit can be implemented by a number of full adder circuits or parallel adder circuits. F

What is artificial intelligence neural networks, For the sake of trying to ...

For the sake of trying to make intelligent behavior though really all that's being done is work with artificial neural networks where every cell is a very easy processor and the go

Determine number of final selector in 10000 line exchange, In a 10000 line ...

In a 10000 line exchange, 0000 to 2999 is allotted to x group of subscribers, out of which 40% are active during busy hour. The remaining numbers are domestic numbers out of which

Data parallel model - parallel programming model, In the data parallel mode...

In the data parallel model, many of the parallel work focus on performing operations on a data set. The data set is usually organized into a common structure, such as an array or a

Explain about fundamental nature of a computer, Q. Explain about fundamenta...

Q. Explain about fundamental nature of a Computer? The fundamental nature of a Computer is as an information transformer. So a computer should be able to take input and process

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