Tuesday, January 14, 2014

Grammar Induction

All objects described are fixed or unique
"John is a student" student(john)
Here John refers to one unique person.

Objects described can be unique or variables to stand for a unique object
"All students are poor"
ForAll(S) [student(S) -> poor(S)]
Here S can be replaced by many different unique students.

This makes programs much more compact:
eg. ForAll(A,B)[brother(A,B) -> brother (B,A)] replaces half the possible statements about brothers

• Temporal => Represents truth over time.
• Modal => Represents doubt
• Higher order logics => Allows variable to represent many relations between objects
• Non-monotonic => Represents defaults

Given clauses C1 and C2, a clause C is a RESOLVENT of C1 and C2, if
1. There is a subset C1' = {A1, .., Am} of C1 of literals of the same sign, say
positive, and a subset C2' = {B1, .., Bn} of C2 of literals of the opposite sign, say
negative,
2. There are substitutions s1 and s2 that replace variables in C1' and C2' so as to
have new variables,
3. C2'' is obtained from C2 removing the negative signs from B1 .. Bn
4. There is an Most General Unifier s for the union of C1'.s1 and C2''.s2
and C is
((C1 - C1').s1 UNION (C2 - C2').s2).s
In symbols this Resolution inference rule becomes:
{C1, C2}

Let L be a list containing the initial state (L= the fringe)

Loop
if L is empty return failure
Node   select (L)
if Node is a goal
then return Node
(the path from initial state to Node)
else generate all successors of Node, and
merge the newly generated states into L

End Loop

No comments:

Post a Comment