160
%doesprovidethoroughcheckingforsmallexamples.(Giventhe
combinatorics,large
%examplesareoutofthequestion.
well_defined_for(LIST):-
not(ordering_counterexample(LIST,A1,A2)),
not(nil_minimal_counterexample(LIST,A)).
%Ifthereisanelementnotgreaterthannil,thispredicate
determinesitsidentity.
nil_minimal_counterexample(LIST,A):-
legal_address_for(LIST,A),
A\=address([],0),
not(less(address([],0),A)).
%Ifthereisapairofaddressesthatisnotproperlyordered,this
predicatefinds
%them.
ordering_counterexample(LIST,A1,A2):-
legal_address_for(LIST,A1),
legal_address_for(LIST,A2),
A1\=A2,
not(less(A1,A2)),
not(less(A2,A1)).
ordering_counterexample(LIST,A1,A2):-
proper_address_for(LIST,A1),
proper_address_for(LIST,A2),
A1\=A2,
not(less(A1,A2)),
not(less(A2,A1)).
%Thispredicatechecksifachangesetisconflicted.
conflicted(LIST):-
member(X,LIST),
member(A,LIST),
X\=A,
dest(X,Y),
dest(A,B),
Y=B.
%Isaregionoftheaddressspacedeletedbyanychangeinthechange
setS?
deleted(A1,A2,S):-
member(X,S),
operation(X,delete(B,E)),
less_eq(B,A1),

161
less_eq(A2,E).
%Thischecksiftheaddressrangeisinthesourceofamove
%foranychangeinS.
moved(A1,A2,S):-
member(M1,S),
operation(M1,move(B,E,_)),
less_eq(B,A1),
less_eq(A2,E).
next_address(LIST,R,T):-
proper_addresses(LIST,ALL),
member(T,ALL),
less(R,T),
not(between(ALL,X,R,T)).
between(ALL,X,R,T):-
member(X,ALL),
member(R,ALL),
member(T,ALL),
less(R,X),
less(X,T).
list_addresses(LIST,V1,[V1|T]):-
next_address(LIST,V1,H2),!,
list_addresses(LIST,H2,T).
list_addresses(LIST,V1,[V1]):-
not(next_address(LIST,V1,X)),!.
address_sequence(List,Result):-
proper_addresses(List,All),mergesort(All,Result).
%EnumerateallmoveswithlowerprioritythanthemovewithIDI.
recessive_moves(I,[],[]).
recessive_moves(I,[M|X],[M|S]):-
is_move(I),
is_move(M),
M=<I,!,
recessive_moves(I,X,S).
recessive_moves(I,X,[M|S]):-
is_move(I),
recessive_moves(I,X,S).