/*********************************************************************

subsumes.pl

Patrick Blackburn, 2000.
Kristina Striegnitz, 2002.

This code is also based on Gazdar and Mellish.

Usage: subsumes(?feature structure, ?feature structure)

Takes as input two feature structures written in our Prolog notation,
and checks whether the first one subsumes the second one.

Strategy: Instantiate all variables in the second feature structur
with atoms. Different variables get different atoms. Then try to
unify. If it works, the subsumption relation holds. (Reason: no new
information has to be added to the second feature structure.)
Otherwise, the subsumption relation does not hold.

Double negation to avoid destructively changing the feature
structures.

NOTE: you have to also consult unify.pl for this to work.

*********************************************************************/


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% subsumes(?feature structure, ?feature structure)

subsumes(F1,F2) :-
	\+ (inst_vars(F2), 
            \+ (unify0(F1,F2))).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% inst_vars(?feature structure)

inst_vars(F) :-
	inst_vars0(F,v(0),_).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% inst_vars0(?feature structure, +current atom, -next atom)

%%% 1st argument is a variable -> instantiate it
inst_vars0(F,I,v(I)) :-
	var(F),!,
	F = I.

%%% 1st arg is the empty list -> do nothing
inst_vars0([],I,I) :- !.

%%% 1st arg is a non-empty list -> instantiate all variables in the
%%% first element and then all variables in the rest
inst_vars0([H|T],I,IOut) :- !,
	inst_vars0(H,I,I0),
	inst_vars0(T,I0,IOut).

%%% 1st arg is a feature value pair -> instantiate all variables in
%%% the value
inst_vars0(_F:V,I,IOut) :- !,
	inst_vars0(V,I,IOut).

%%% do nothing in all other cases
inst_vars0(_,I,I).	


/**********************************************************************
                    That's all, folks!
***********************************************************************/