CEng242 Homework 6
Due 26$^{th}$ May 2002

In some symbolic systems like natural language processing systems information of an entity is represented in the form of feature structures. Feature structures are nested feature-value pairs where feature represents the name of the feature and value is the value of it. Feature names are atomic and constants but values can be atomic, variable or another feature structure so nesting is possible. The notation used to represent feature structure is also called Attribute Value Matrices:

$A$		$B$

First feature structure A above represents some features of a family consisting of a father, mother and the son. Some information is available but some is skipped (i.e. occupation of the mother). Second represents less information, only some features of mother and the father.

A feature can have only one value in a feature structure. Same feature name cannot be repeated even values are compatible.

In such representation of information, a subsumption (or extension) relation is defined among all feature structures. When a feature structure $A$ is subsumed by feature structure $B$ ($A$ extends $B$, $A \preceq B$, that means $A$ has all information content available in $B$ and may contain further information. So that we can say that $A$ is at least as informative as $B$ and possibly more informative than $B$. For example the feature structure $A$ in the example is more informative than $B$, it contains all information in it. So $A$ extends $B$.

Also we can infer that if $A \preceq B$, $B$ is more general than $A$, or $A$ is more specific than $B$, since the information in $B$ defines a larger group of entities, on the other hand the information in $A$ makes it narrower by having more features specified.

Please note that for extend relation to hold, all common feature paths should have compatible values and information in one structure should be fully available in the other. For example there is no extend relation defined between `[ name hasan ]' and `[ age 50 ]' since none of them contains the others information. Similarly no relation holds between `[ name hasan ]' and `[ name hatice ]' since the values are not compatible.

The maximal element of this relation is Top, $\top$, where $\forall x, x \preceq \top$. It is also denoted with empty feature structure $[ ]$, which means no information. Also the minimal element is Bottom, $\bot$, which denotes the inconsistent information. So $\forall x, \bot \preceq x$.

A binary operation most general unifier is defined on feature structures and represented by $\wedge$. It gives the most general (least informative) feature structure that extends both feature structures. So if $C = A \wedge B$ then $C$ is the most general feature structure having $C \preceq A, C \preceq B$.

Another operation least general subsumer represented by $\vee$ gives a least general (more informative) feature structure subsuming both structures. So if $C = A \vee B$ then $C$ is the most specific feature structure having $A \preceq C, B \preceq C$.

Most general unifier gives a feature structure combining information available in either operands and the new structure will be more informative than both. Least general subsumer gives only the information available in both operands and the new structure will contain an intersection of information in the operands.

In this homework you will write a Prolog program to implement:

• The relation extends(A,B) checking if $A \preceq B$.
• The operation mgu(A,B,C) giving $C = A \wedge B$.
• The operation lgs(A,B,C) giving $C = A \vee B$.

You will represent a feature structure as a list of Feat-Val pairs where order is not important. Feat is an atom and Val is either any prolog term which is not a list, or a feature structure list. Note that Feat-Val is an infix notation for prolog term -(Feat,Val).

So the feature structure $B$ above is represented by the prolog list:
[father-[name-ahmet,occupation-farmer],mother-[name-hatice]]
and $A$ is represented by:

[ father-[ name-ahmet,
           age-32,
           occupation-farmer,
           hobbies-[ play-basketball,
                     read-history
                   ] ],
  mother-[ name-hatice,
           age-30,
           hobbies-[ sing-turkishclassic,
                     play-tenis
                   ] ],
  son-[ name-hicabi,
        age-5,
        dimensions-[ weight-25,
                     height-95
                   ] ]
]

Examples:

?- extends([class-hatchback,maxspeed-300] , [class-hatchback]).
yes
?- extends([class-hatchback] , [class-hatchback,color-300]).
no
?- extends([class-hatchback,maxspeed-300] , [color-red,class-hatchback]).
no
?- mgu([class-hatchback,maxspeed-300] , [color-red,class-hatchback] ,  C).
C=[class-hatchback,maxspeed-300,color-red] 
?- lgs([class-hatchback,maxspeed-300] , [color-red,class-hatchback] ,  C).
C=[class-hatchback]

You can define any helper clause. But your program should give only unique solutions. No ambiguities or repetitions allowed and it should be provided implicitly. Producing ambiguities and then eliminating is not acceptable. I'm giving a prettyprint predicate to show your feature structures in a neat way:

spaces(0).
spaces(N) :- N > 0, M is N-1,write(' '),spaces(M).
pretty2([],_).
pretty2([H|T],N) :- write(','),nl,spaces(N),prettyprint(H,N),
                        pretty2(T,N).
prettyprint(L) :- prettyprint(L,0).
prettyprint(F-V,N) :- !,write(F),write(': '), name(F,Fname),length(Fname,K),
                        M is N+K+2,
                        prettyprint(V,M).
prettyprint([H|T],N) :- !,write('[ '),M is N+2,
                        prettyprint(H,M),
                        pretty2(T,M),nl,
                        spaces(N),write(']').
prettyprint(A,_) :- write(A).

You can use it in the following way:

?- prettyprint([father-[name-ahmet,age-32,occupation-farmer,
   hobbies-[play-basketball,read-history]],
   mother-[name-hatice,age-30,hobbies-[sing-turkishclassic,play-tenis]],
   son-[name-hicabi,age-5,dimensions-[weight-25,height-95]]]).

[ father: [ name: ahmet,
            age: 32,
            occupation: farmer,
            hobbies: [ play: basketball,
                       read: history
                     ]
          ],
  mother: [ name: hatice,
            age: 30,
            hobbies: [ sing: turkishclassic,
                       play: tenis
                     ]
          ],
  son: [ name: hicabi,
         age: 5,
         dimensions: [ weight: 25,
                       height: 95
                     ]
       ]
]
yes

Detailed examples will follow.