Unification algorithm - artificial intelligence, Computer Engineering

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

Posted Date: 10/2/2012 9:30:13 AM | Location : United States

Related Discussions:- Unification algorithm - artificial intelligence, Assignment Help, Ask Question on Unification algorithm - artificial intelligence, Get Answer, Expert's Help, Unification algorithm - artificial intelligence Discussions

Write discussion on Unification algorithm - artificial intelligence
Your posts are moderated
Related Questions
Describe the additional characteristics needed for an e-commerce server? E-commerce services need dynamic configuration abilities and seasonal and every day service configurat

Hyper-threading works by duplicating those sections of processor that kept the architectural state-but not duplicates the main implementation resources. This allows a Hyper-threadi

In a positive logic system, logic state 1 corresponds to ? Ans. For positive digital logic, we choose two voltages levels. Higher voltage shows logic 1 and a lower voltage sho

State about CSMA/CA It belongs to a class of protocols known as multiple access methods. CSMA/CA  stands  for:  Carrier  Sense  Multiple  Access  with  Collision Avoidance.  In

Problem: (i) What are the main threats that an organisation holding sensitive data, such as Public Data, on computer storage must guard against? (ii) To protect such data,

Q. Illustrate about Packet switching? Packet switching is used to avoid long delays in transmitting data over the network. Packet switching is a technique that limits the amoun

Draw a circuit of an NMOS inverter and explain its operation

Detemine the major building blocks of UML UML could be used in visualizing, specifying, constructing and documenting object oriented systems. The major building blocks of UML a

For each of the following variables: YEARofBIRTH transformed into a new variable called . To do this you will need to use the Command. Hint codes 9998 and 9999 are missin

What is a Data Class? The Data class verifies in which table space the table is stored when it is formed in the database