% A Weighted Tree Similarity Algorithm in OO RuleML Relfun      25 Apr 2003
% ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


% Assumes both weighted trees are already in a 'lexicographic' normal form
% (roles branch off in 'alphabetic' order).

% Tree representation uses OO RuleML syntax in Relfun, where roles start
% with a "-", not with a "_" (free in XML, but variable prefix of Relfun):
% http://www.ruleml.org/indoo

% Uses the parameter N(ode) for specifying the fraction to which the equality
% of tree-root node labels is counted relative to the result of the recursive
% comparison of its list of subtrees. 

% Uses the functional parameter A(djust), which can be the id(enti)ty, sqrt,
% etc., for compensating similarity degradation for nested trees.

% A binary function, treesim, computes the similarity between its two tree
% arguments, co-recursively calling treemap, which sums up the similarities
% of its two lists of (sub)trees. We assume that the weights in each subtree
% fan-out sum up to 1. Here, 1 means total similarity; 0 represents absolute
% dissimilarity. Since treesim is symmetric in its two arguments, some of the
% algorithm's clauses could be simplified (incurring an efficiency penalty).

% Analogously, a unary function, treeplicity computes the simplicity of its
% single tree arguments, co-recursively calling treeplimap. The simplicity
% measure is used by the similarity measure for subtrees occurring in only one
% of the trees. Here, 1 means total simplicity; 0 (never to be reached) would
% represent infinite complexity.

% Only the deterministic, functional subset of Relfun is required, where
% '!&' is the 'cut-return' infix and "lhs :- cond !& rhs" stands for the
% conditional equation "lhs if cond cut-return rhs" or "lhs = rhs if cond";
% the unconditional equation "lhs !& rhs" abbreviates "lhs :- true !& rhs".
% Built-ins are taken from Common Lisp. E.g., string< and string> compare
% two string or symbol arguments for 'lexicographic' less and greater order.

% Runs at http://serv-4100.dfki.uni-kl.de:8000/~vega/cgi-bin/rfi



% Paste the program into the above URL's Database window:



treesim[N,A](ind[Leaf],ind[Leaf]) !& 1.    % Same leaves

treesim[N,A](ind[Leaf1],ind[Leaf2]) !& 0.  % Different leaves

treesim[N,A](cterm[ -opc[ctor[Label]]      % Same node Label
                    ],
             cterm[ -opc[ctor[Label]]      % on two empty trees:
                    ])
        !& 1.                              % 1

treesim[N,A](cterm[ -opc[ctor[Label]]      % Same node Label on two trees,
                    | Rest1 ],
             cterm[ -opc[ctor[Label]]      % one or both being non-empty:
                    | Rest2 ])
        !&
            +(N,                                  % add N(ode) fraction
              *( -(1,N),                          % to 1-N fraction of
                 treemap[N,A](Rest1,Rest2) ) ).   % subtree list comparison

treesim[N,A](cterm[ -opc[ctor[Label1]]     % Different node Labels
                    | Rest1 ],
             cterm[ -opc[ctor[Label2]]     % on arbitrary trees:
                    | Rest2 ])
        !& 0.                              % 0

treesim[N,A](ind[Label],                   % Same Label on leaf and on
             cterm[ -opc[ctor[Label]]      % arbitrary tree (e.g. empty):
                    | Rest ])
        !&
            treesim[N,A](cterm[ -opc[ctor[Label]] % Substitute empty tree
                                ],
                         cterm[ -opc[ctor[Label]]
                                | Rest ]).

treesim[N,A](cterm[ -opc[ctor[Label]]      % Same Label on arbitrary tree
                    | Rest ],
             ind[Label])                   % (e.g. empty) and on leaf:
        !&
            treesim[N,A](cterm[ -opc[ctor[Label]]
                                | Rest ],
                         cterm[ -opc[ctor[Label]] % Substitute empty tree
                                ]).

treesim[N,A](ind[Label1],                   % Different Labels on leaf and
             cterm[ -opc[ctor[Label2]]      % on arbitrary tree (e.g. empty):
                    | Rest ])
        !& 0.                               % 0

treesim[N,A](cterm[ -opc[ctor[Label1]]      % Different Labels on arbitrary
                    | Rest ],               % tree (e.g. empty)
             ind[Label2])                   % and on leaf:
        !& 0.                               % 0



treemap[N,A]([],[]) !& 0.

treemap[N,A]([ First | Rest ],
             [])                                  % no Role1 in empty T2
       !&
            +( *( 0.5,treeplicity(-(1,N),
                                  cterm[ -opc[ctor[Label]],First ])),
               treemap[N,A](Rest,[]) ).

treemap[N,A]([],                                  % no Role2 in empty T1
             [ First | Rest ])
       !&
            +( *( 0.5,treeplicity(-(1,N),
                                  cterm[ -opc[ctor[Label]],First ])),
               treemap[N,A]([],Rest) ).

treemap[N,A]([ -r[n[Role],w[Weight1]][Subtree1]   % T1 and T2 start
               | Rest1 ],
             [ -r[n[Role],w[Weight2]][Subtree2]   % with same role
               | Rest2 ])
       !&                                               % With assumption
            +( *( /( +(Weight1,Weight2),2),             % Weight sum = 1:
                  A(treesim[N,A](Subtree1,Subtree2))),  % A(djusted) sub-
               treemap[N,A](Rest1,Rest2) ).             % tree comparison

treemap[N,A]([ -r[n[Role1],w[Weight1]][Subtree1]
               | Rest1 ],
             [ -r[n[Role2],w[Weight2]][Subtree2]
               | Rest2 ])
       :-
            string<(Role1,Role2)                     % Role1 missing in T2
       !&
            +( *( 0.5,
                  treeplicity(-(1,N),
                              cterm[ -opc[ctor[Label]],
                                     -r[n[Role1],w[Weight1]][Subtree1] ])),
               treemap[N,A](Rest1,
                            [ -r[n[Role2],w[Weight2]][Subtree2]
                              | Rest2 ]) ).

treemap[N,A]([ -r[n[Role1],w[Weight1]][Subtree1]
               | Rest1 ],
             [ -r[n[Role2],w[Weight2]][Subtree2]
               | Rest2 ])
       :-
            string>(Role1,Role2)                     % Role2 missing in T1
       !&
            +( *( 0.5,
                  treeplicity(-(1,N),
                              cterm[ -opc[ctor[Label]],
                                     -r[n[Role2],w[Weight2]][Subtree2] ])),
               treemap[N,A]([ -r[n[Role1],w[Weight1]][Subtree1]
                              | Rest1 ],
                            Rest2) ).



treeplicity(I,ind[Leaf]) !& I.             % I: Current depth degradation value

treeplicity(I,cterm[-opc[ctor[Label]]]) !& I. % (initialized with 1-N fraction)

treeplicity(I,cterm[ -opc[ctor[Label]],First | Rest ])
      !&
           *( /(1,1+(len(Rest))),        %    Breadth degradation factor
              treeplimap(I,[First | Rest ])).


treeplimap(I,[]) !& 0.

treeplimap(I,[-r[n[Role],w[Weight]][Subtree]
              | Rest ])
      !&
           +(*(Weight,treeplicity(*(treeplideg(),I),Subtree)),
             treeplimap(I,Rest)).


treeplideg() !& 0.5.    % Depth degradation factor (change global constant here)



idty(X) !& X.   % Functional parameter for A(rc-adjusted) comparison

% More functions for A(rc-adjusted) comparison

adjust1(X)  !& sqrt(sqrt(X)).
adjust2(X)  !& sin(*(/(3.1415926535,2),X)).
adjust3(X)  !& sqrt(X).
adjust4(X)  !& X. % idty
adjust5(X)  !& sqrt(expt(X,3)).




% Paste the sample inputs into the above URL's Query window:


treeplicity(1.0,
cterm[
   -opc[ctor[auto]],
   -r[n[year],w[1.0]][ind[1]]
     ])


treeplicity(1.0,
cterm[
   -opc[ctor[auto]],
   -r[n[year],w[1.0]][cterm[
                         -opc[ctor[auto]],
                         -r[n[year],w[1.0]][ind[1]]
                           ]]
     ])


treeplicity(1.0,
cterm[
   -opc[ctor[auto]],
   -r[n[year],w[1.0]][cterm[
                         -opc[ctor[auto]],
                         -r[n[year],w[1.0]][cterm[
                                               -opc[ctor[auto]],
                                               -r[n[year],w[1.0]][ind[1]]
                                           ]]
                           ]]
     ])


treeplicity(1.0,
cterm[
   -opc[ctor[auto]],
   -r[n[year],w[1.0]][cterm[
                         -opc[ctor[auto]],
                         -r[n[year],w[1.0]][cterm[
                                               -opc[ctor[auto]],
                                               -r[n[year],w[1.0]][cterm[
                                                                     -opc[ctor[auto]],
                                                            -r[n[year],w[1.0]][ind[1]]
                                                                 ]]
                                           ]]
                           ]]
     ])



treeplicity(1.0,
cterm[
   -opc[ctor[auto]],
   -r[n[year],w[0.02]][ind[10]],
   -r[n[make],w[0.02]][ind[9]],
   -r[n[model],w[0.02]][ind[8]],
   -r[n[year],w[0.02]][ind[7]],
   -r[n[make],w[0.02]][ind[6]],
   -r[n[model],w[0.02]][ind[5]],
   -r[n[year],w[0.02]][ind[4]],
   -r[n[make],w[0.02]][ind[3]],
   -r[n[model],w[0.02]][ind[2]],
   -r[n[year],w[0.02]][ind[1]],
   -r[n[year],w[0.02]][ind[10]],
   -r[n[make],w[0.02]][ind[9]],
   -r[n[model],w[0.02]][ind[8]],
   -r[n[year],w[0.02]][ind[7]],
   -r[n[make],w[0.02]][ind[6]],
   -r[n[model],w[0.02]][ind[5]],
   -r[n[year],w[0.02]][ind[4]],
   -r[n[make],w[0.02]][ind[3]],
   -r[n[model],w[0.02]][ind[2]],
   -r[n[year],w[0.02]][ind[1]],
   -r[n[year],w[0.02]][ind[10]],
   -r[n[make],w[0.02]][ind[9]],
   -r[n[model],w[0.02]][ind[8]],
   -r[n[year],w[0.02]][ind[7]],
   -r[n[make],w[0.02]][ind[6]],
   -r[n[model],w[0.02]][ind[5]],
   -r[n[year],w[0.02]][ind[4]],
   -r[n[make],w[0.02]][ind[3]],
   -r[n[model],w[0.02]][ind[2]],
   -r[n[year],w[0.02]][ind[1]],
   -r[n[year],w[0.02]][ind[10]],
   -r[n[make],w[0.02]][ind[9]],
   -r[n[model],w[0.02]][ind[8]],
   -r[n[year],w[0.02]][ind[7]],
   -r[n[make],w[0.02]][ind[6]],
   -r[n[model],w[0.02]][ind[5]],
   -r[n[year],w[0.02]][ind[4]],
   -r[n[make],w[0.02]][ind[3]],
   -r[n[model],w[0.02]][ind[2]],
   -r[n[year],w[0.02]][ind[1]],
   -r[n[year],w[0.02]][ind[10]],
   -r[n[make],w[0.02]][ind[9]],
   -r[n[model],w[0.02]][ind[8]],
   -r[n[year],w[0.02]][ind[7]],
   -r[n[make],w[0.02]][ind[6]],
   -r[n[model],w[0.02]][ind[5]],
   -r[n[year],w[0.02]][ind[4]],
   -r[n[make],w[0.02]][ind[3]],
   -r[n[model],w[0.02]][ind[2]],
   -r[n[year],w[0.02]][ind[1]]
                   ])


treeplicity(1.0,
cterm[
   -opc[ctor[auto]],
   -r[n[year],w[0.1]][ind[10]],
   -r[n[make],w[0.1]][ind[9]],
   -r[n[model],w[0.1]][ind[8]],
   -r[n[year],w[0.1]][ind[7]],
   -r[n[make],w[0.1]][ind[6]],
   -r[n[model],w[0.1]][ind[5]],
   -r[n[year],w[0.1]][ind[4]],
   -r[n[make],w[0.1]][ind[3]],
   -r[n[model],w[0.1]][ind[2]],
   -r[n[year],w[0.1]][ind[1]]
                   ])


treeplicity(1.0,
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.1112]][ind[9]],
   -r[n[model],w[0.1111]][ind[8]],
   -r[n[year],w[0.1111]][ind[7]],
   -r[n[make],w[0.1111]][ind[6]],
   -r[n[model],w[0.1111]][ind[5]],
   -r[n[year],w[0.1111]][ind[4]],
   -r[n[make],w[0.1111]][ind[3]],
   -r[n[model],w[0.1111]][ind[2]],
   -r[n[year],w[0.1111]][ind[1]]
                   ])


treeplicity(1.0,
cterm[
   -opc[ctor[auto]],
   -r[n[model],w[0.125]][ind[8]],
   -r[n[year],w[0.125]][ind[7]],
   -r[n[make],w[0.125]][ind[6]],
   -r[n[model],w[0.125]][ind[5]],
   -r[n[year],w[0.125]][ind[4]],
   -r[n[make],w[0.125]][ind[3]],
   -r[n[model],w[0.125]][ind[2]],
   -r[n[year],w[0.125]][ind[1]]
                   ])



treeplicity(1.0,
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.334]][ind[3]],
   -r[n[model],w[0.333]][ind[2]],
   -r[n[year],w[0.333]][ind[1]]
                   ])


treeplicity(1.0,
cterm[
   -opc[ctor[auto]],
   -r[n[model],w[0.5]][ind[2]],
   -r[n[year],w[0.5]][ind[1]]
                   ])

treeplicity(1.0,
cterm[
   -opc[ctor[auto]],
   -r[n[model],w[0.6]][ind[2]],
   -r[n[year],w[0.4]][ind[1]]
                   ])

treeplicity(1.0,
cterm[
   -opc[ctor[auto]],
   -r[n[model],w[0.7]][ind[2]],
   -r[n[year],w[0.3]][ind[1]]
                   ])

treeplicity(1.0,
cterm[
   -opc[ctor[auto]],
   -r[n[model],w[0.8]][ind[2]],
   -r[n[year],w[0.2]][ind[1]]
                   ])


treeplicity(1.0,
cterm[
   -opc[ctor[auto]],
   -r[n[year],w[1.0]][ind[1]]
                   ])


treeplicity(1.0,
cterm[
   -opc[ctor[auto]]
                   ])



treeplicity(1.0,cterm[-opc[ctor[Label]],
                  -r[n[make],w[0.7]][ind[ford]]]) 

treeplicity(1.0,cterm[-opc[ctor[Label]],
                  -r[n[model],w[0.1]][ind[explorer]]]) 


treeplicity(1.0,cterm[-opc[ctor[Label]],
                  -r[n[make],w[0.7]][ind[ford]],
                  -r[n[model],w[0.1]][ind[explorer]]])




treesim[0.1,idty](
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.0]][ind[ford]],
   -r[n[year],w[1.0]][ind[2002]]
],
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[1.0]][ind[chrysler]],
   -r[n[year],w[0.0]][ind[1998]]
])



treesim[0.0,idty](
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.0]][ind[ford]],
   -r[n[year],w[1.0]][ind[2002]]
],
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[1.0]][ind[chrysler]],
   -r[n[year],w[0.0]][ind[1998]]
])



treesim[0.0,idty](
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.0]][ind[chrysler]],
   -r[n[year],w[1.0]][ind[2002]]
],
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[1.0]][ind[chrysler]],
   -r[n[year],w[0.0]][ind[1998]]
])



treesim[0.0,idty](
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.0]][ind[chrysler]],
   -r[n[year],w[1.0]][ind[2002]]
],
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[1.0]][ind[chrysler]],
   -r[n[year],w[0.0]][ind[2002]]
])



treesim[0.1,idty](
cterm[
-opc[ctor[auto]],
-r[n[model],w[1.0]][ind[mustang]]
],
cterm[
-opc[ctor[auto]],
-r[n[make],w[0.45]][ind[ford]],
-r[n[model],w[0.1]][ind[explorer]],
-r[n[year],w[0.45]][ind[2000]]
])

treesim[0.1,idty](
cterm[
-opc[ctor[auto]],
-r[n[model],w[1.0]][ind[mustang]]
],
cterm[
-opc[ctor[auto]],
-r[n[make],w[0.05]][ind[ford]],
-r[n[model],w[0.9]][ind[explorer]],
-r[n[year],w[0.05]][ind[2000]]
])

treesim[0.1,idty](
cterm[
-opc[ctor[auto]],
-r[n[model],w[1.0]][ind[mustang]]
],
cterm[
-opc[ctor[auto]],
-r[n[make],w[0.7]][ind[ford]],
-r[n[model],w[0.1]][ind[explorer]],
-r[n[year],w[0.2]][ind[2000]]
])

treesim[0.1,idty](
cterm[
-opc[ctor[auto]],
-r[n[year],w[1.0]][ind[1999]]
],
cterm[
-opc[ctor[auto]],
-r[n[make],w[0.7]][ind[ford]],
-r[n[model],w[0.1]][ind[explorer]],
-r[n[year],w[0.2]][ind[2000]]
])

treesim[0.1,idty](
cterm[
-opc[ctor[auto]],
-r[n[model],w[0.8]][ind[mustang]],
-r[n[year],w[0.2]][ind[1999]]
],
cterm[
-opc[ctor[auto]],
-r[n[make],w[0.7]][ind[ford]],
-r[n[model],w[0.1]][ind[explorer]],
-r[n[year],w[0.2]][ind[2000]]
])


treesim[0.1,idty](
cterm[
-opc[ctor[auto]],
-r[n[model],w[1.0]][ind[mustang]]
],
cterm[
-opc[ctor[auto]],
-r[n[make],w[0.3333]][ind[ford]],
-r[n[model],w[0.3334]][ind[explorer]],
-r[n[year],w[0.3333]][ind[2000]]
])

treesim[0.1,idty](
cterm[
-opc[ctor[auto]],
-r[n[year],w[1.0]][ind[1999]]
],
cterm[
-opc[ctor[auto]],
-r[n[make],w[0.3333]][ind[ford]],
-r[n[model],w[0.3333]][ind[explorer]],
-r[n[year],w[0.3334]][ind[2000]]
])

treesim[0.1,idty](
cterm[
-opc[ctor[auto]],
-r[n[model],w[0.3333]][ind[mustang]],
-r[n[year],w[0.3333]][ind[1999]]
],
cterm[
-opc[ctor[auto]],
-r[n[make],w[0.3334]][ind[ford]],
-r[n[model],w[0.3333]][ind[explorer]],
-r[n[year],w[0.3333]][ind[2000]]
])




treesim[0.1,idty](
cterm[-opc[ctor[explorer]]],
cterm[-opc[ctor[explorer]]])



treesim[0.1,idty](
cterm[-opc[ctor[mustang]]],
cterm[-opc[ctor[explorer]]])



treesim[0.1,idty](
ind[explorer],
cterm[-opc[ctor[explorer]]])



treesim[0.1,idty](
cterm[ -opc[ctor[car]],
            -r[n[make],w[0.3]][ind[ford]],
            -r[n[model],w[0.2]][ind[explorer]],  
            -r[n[year],w[0.5]][ind[2002]]
           ],
cterm[ -opc[ctor[car]],
            -r[n[make],w[0.3]][ind[ford]],
            -r[n[model],w[0.2]][ind[explorer]],  
            -r[n[year],w[0.5]][ind[1999]]
           ]
)



treesim[0.1,idty](
cterm[ -opc[ctor[car]],
            -r[n[make],w[0.3334]][ind[ford]],
            -r[n[model],w[0.3333]][ind[explorer]],  
            -r[n[year],w[0.3333]][ind[2002]]
           ],
cterm[ -opc[ctor[car]],
            -r[n[make],w[0.3334]][ind[ford]],
            -r[n[model],w[0.3333]][ind[explorer]],  
            -r[n[year],w[0.3333]][ind[1999]]
           ]
)



treesim[0.1,idty](
cterm[
   -opc[ctor[auto]]
],
cterm[
   -opc[ctor[auto]]
])



treesim[0.1,idty](
cterm[
   -opc[ctor[auto]]
],
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[1.0]][ind[ford]]
])



treesim[0.1,idty](
cterm[
   -opc[ctor[auto]]
],
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.5]][ind[ford]],
   -r[n[model],w[0.5]][ind[explorer]]
])



treesim[0.1,idty](
cterm[
   -opc[ctor[auto]]
],
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[explorer]],
   -r[n[year],w[0.3333]][ind[1999]]
])



treesim[0.1,idty](
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[1.0]][ind[ford]]
],
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.5]][ind[ford]],
   -r[n[model],w[0.5]][ind[explorer]]
])



treesim[0.1,idty](
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[1.0]][ind[ford]]
],
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[explorer]],
   -r[n[year],w[0.3333]][ind[1999]]
])



treesim[0.1,idty](
cterm[
   -opc[ctor[auto]]
],
cterm[
   -opc[ctor[auto]]
])



treesim[0.1,idty](
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[1.0]][ind[ford]]
],
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[1.0]][ind[ford]]
])



treesim[0.1,idty](
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.5]][ind[ford]],
   -r[n[model],w[0.5]][ind[explorer]]
],
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.5]][ind[ford]],
   -r[n[model],w[0.5]][ind[explorer]]
])


treesim[0.1,idty](
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[explorer]],
   -r[n[year],w[0.3333]][ind[1999]]
],
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[explorer]],
   -r[n[year],w[0.3333]][ind[1999]]
])



treesim[0.1,idty](
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[explorer]],
   -r[n[year],w[0.3333]][ind[1999]]
],
cterm[
   -opc[ctor[car]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[explorer]],
   -r[n[year],w[0.3333]][ind[1999]]
])



treesim[0.1,idty](
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[explorer]],
   -r[n[year],w[0.3333]][ind[1999]]
],
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][cterm[-opc[ctor[explorer]]]],
   -r[n[year],w[0.3333]][ind[1999]]
])



treesim[0.1,idty](
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.7]][ind[ford]],
   -r[n[model],w[0.1]][ind[mustang]],
   -r[n[year],w[0.2]][ind[1999]]
],
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.7]][ind[ford]],
   -r[n[model],w[0.1]][ind[explorer]],
   -r[n[year],w[0.2]][ind[2000]]
])

% idty: 0.7



treesim[0.1,idty](
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.7]][ind[ford]],
   -r[n[model],w[0.1]][ind[mustang]],
   -r[n[year],w[0.2]][ind[1999]]
],
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.8]][ind[ford]],
   -r[n[year],w[0.2]][ind[2000]]
])

% idty: 0.775



treesim[0.1,idty](
cterm[
   -opc[ctor[auto]],
   -r[n[model],w[0.8]][ind[mustang]],
   -r[n[year],w[0.2]][ind[1999]]
],
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.7]][ind[ford]],
   -r[n[model],w[0.1]][ind[explorer]],
   -r[n[year],w[0.2]][ind[2000]]
])

% idty: 0.1 (no similarity measure over leaves)



treesim[0.1,idty](
cterm[
   -opc[ctor[auto]],
   -r[n[model],w[0.8]][ind[mustang]],
   -r[n[year],w[0.2]][ind[1999]]
],
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.7]][ind[ford]],
   -r[n[model],w[0.1]][ind[explorer]],
   -r[n[year],w[0.2]][ind[1999]]
])

% idty: 0.28



treesim[0.1,idty](
cterm[
   -opc[ctor[auto]],
   -r[n[model],w[0.8]][ind[mustang]],
   -r[n[year],w[0.2]][ind[1999]]
],
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.7]][ind[ford]],
   -r[n[model],w[0.1]][ind[mustang]],
   -r[n[year],w[0.2]][ind[1999]]
])

% idty: 0.68500006



treesim[0.1,sqrt](
cterm[
-opc[ctor[vehicle]],
-r[n[autumn],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[explorer]],
   -r[n[year],w[0.3333]][ind[1999]]
]],
-r[n[summer],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[mustang]],
   -r[n[year],w[0.3333]][ind[2000]]
]]],
cterm[
-opc[ctor[vehicle]],
-r[n[autumn],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[explorer]],
   -r[n[year],w[0.3333]][ind[1994]]
]],
-r[n[summer],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[mustang]],
   -r[n[year],w[0.3333]][ind[2001]]
]]]
)

% idty: 0.730027
% sqrt: 0.8530102



treesim[0.1,sqrt](
cterm[
-opc[ctor[vehicle]],
-r[n[autumn],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.5]][ind[ford]],

   -r[n[year],w[0.5]][ind[1999]]
]],
-r[n[summer],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[mustang]],
   -r[n[year],w[0.3333]][ind[2000]]
]]],
cterm[
-opc[ctor[vehicle]],
-r[n[autumn],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[explorer]],
   -r[n[year],w[0.3333]][ind[1994]]
]],
-r[n[summer],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[mustang]],
   -r[n[year],w[0.3333]][ind[2001]]
]]]
)

% idty: 0.628777
% sqrt: 0.78665596



treesim[0.1,sqrt](
cterm[
-opc[ctor[vehicle]],
-r[n[autumn],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.5]][ind[ford]],

   -r[n[year],w[0.5]][ind[1999]]
]],
-r[n[summer],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[mustang]],
   -r[n[year],w[0.3333]][ind[2000]]
]]],
cterm[
-opc[ctor[vehicle]],
-r[n[autumn],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.5]][ind[ford]],
   -r[n[model],w[0.5]][ind[explorer]]

]],
-r[n[summer],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[mustang]],
   -r[n[year],w[0.3333]][ind[2001]]
]]]
)

% idty: 0.66251355
% sqrt: 0.810234



treesim[0.1,sqrt](
cterm[
-opc[ctor[vehicle]],

-r[n[summer],w[1.0]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[mustang]],
   -r[n[year],w[0.3333]][ind[2000]]
]]],
cterm[
-opc[ctor[vehicle]],
-r[n[autumn],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[explorer]],
   -r[n[year],w[0.3333]][ind[1994]]
]],
-r[n[summer],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[mustang]],
   -r[n[year],w[0.3333]][ind[2001]]
]]]
)

% idty: 0.57252026
% sqrt: 0.6647576



treesim[0.1,sqrt](
cterm[
-opc[ctor[vehicle]],
-r[n[autumn],w[0.8]][
                      cterm[
                      -opc[ctor[auto]],
                      -r[n[make],w[0.2]][ind[ford]],
                      -r[n[model],w[0.5]][
                        cterm[
                          -opc[ctor[sports]],
                          -r[n[e1],w[0.5]][ind[explorer]],
                          -r[n[e2],w[0.5]][ind[escape]]
                        ]],
                      -r[n[year],w[0.3]][ind[1999]]
                    ]],
-r[n[summer],w[0.2]][
                      cterm[
                      -opc[ctor[auto]],
                      -r[n[make],w[0.8]][ind[ford]],
                      -r[n[model],w[0.1]][
                          cterm[
                            -opc[ctor[sedans]],
                            -r[n[e3],w[0.4]][ind[taurus]],
                            -r[n[e4],w[0.6]][ind[focus]]
                          ]],
                      -r[n[year],w[0.1]][ind[2000]]
                    ]]],

cterm[
-opc[ctor[vehicle]],
-r[n[autumn],w[0.3]][
                     cterm[
                     -opc[ctor[auto]],
                     -r[n[make],w[0.6]][ind[ford]],
                     -r[n[model],w[0.3]][
                          cterm[
                            -opc[ctor[sports]],
                            -r[n[e1],w[0.7]][ind[explorer]],
                            -r[n[e2],w[0.3]][ind[escape]]
                          ]],
                      -r[n[year],w[0.1]][ind[1999]]
                    ]],
-r[n[summer],w[0.7]][
                     cterm[
                     -opc[ctor[auto]],
                     -r[n[make],w[0.2]][ind[ford]],
                     -r[n[model],w[0.2]][ind[sports]],
                     -r[n[year],w[0.6]][ind[2001]]
                   ]]]
)


% idty: 0.81775004
% sqrt: 0.89535606


treesim[0.1,adjust1](
cterm[
-opc[ctor[vehicle]],
-r[n[autumn],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[explorer]],
   -r[n[year],w[0.3333]][ind[1999]]
]],
-r[n[summer],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[mustang]],
   -r[n[year],w[0.3333]][ind[2000]]
]]],
cterm[
-opc[ctor[vehicle]],
-r[n[autumn],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[explorer]],
   -r[n[year],w[0.3333]][ind[1994]]
]],
-r[n[summer],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[mustang]],
   -r[n[year],w[0.3333]][ind[2001]]
]]]
)

%adjust1: 0.9232
%adjust2: 0.9019
%adjust3: 0.8530102
%adjust4: 0.730027
%adjust5: 0.6271


treesim[0.1,adjust1](
cterm[
-opc[ctor[vehicle]],
-r[n[autumn],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.5]][ind[ford]],

   -r[n[year],w[0.5]][ind[1999]]
]],
-r[n[summer],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[mustang]],
   -r[n[year],w[0.3333]][ind[2000]]
]]],
cterm[
-opc[ctor[vehicle]],
-r[n[autumn],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[explorer]],
   -r[n[year],w[0.3333]][ind[1994]]
]],
-r[n[summer],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[mustang]],
   -r[n[year],w[0.3333]][ind[2001]]
]]]
)

%adjust1: 0.8950
%adjust2: 0.8324
%adjust3: 0.8032
%adjust4: 0.6522
%adjust5: 0.5358


treesim[0.1,adjust1](
cterm[
-opc[ctor[vehicle]],
-r[n[autumn],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.5]][ind[ford]],

   -r[n[year],w[0.5]][ind[1999]]
]],
-r[n[summer],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[mustang]],
   -r[n[year],w[0.3333]][ind[2000]]
]]],
cterm[
-opc[ctor[vehicle]],
-r[n[autumn],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.5]][ind[ford]],
   -r[n[model],w[0.5]][ind[explorer]]

]],
-r[n[summer],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[mustang]],
   -r[n[year],w[0.3333]][ind[2001]]
]]]
)

%adjust1: 0.9241
%adjust2: 0.9039
%adjust3: 0.8547
%adjust4: 0.7328
%adjust5: 0.6307


treesim[0.1,adjust1](
cterm[
-opc[ctor[vehicle]],

-r[n[summer],w[1.0]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[mustang]],
   -r[n[year],w[0.3333]][ind[2000]]
]]],
cterm[
-opc[ctor[vehicle]],
-r[n[autumn],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[explorer]],
   -r[n[year],w[0.3333]][ind[1994]]
]],
-r[n[summer],w[0.5]][
cterm[
   -opc[ctor[auto]],
   -r[n[make],w[0.3334]][ind[ford]],
   -r[n[model],w[0.3333]][ind[mustang]],
   -r[n[year],w[0.3333]][ind[2001]]
]]]
)

%adjust1: 0.7676
%adjust2: 0.7516
%adjust3: 0.7149
%adjust4: 0.6227
%adjust5: 0.5455


treesim[0.1,adjust1](
cterm[
-opc[ctor[vehicle]],
-r[n[autumn],w[0.8]][
                      cterm[
                      -opc[ctor[auto]],
                      -r[n[make],w[0.2]][ind[ford]],
                      -r[n[model],w[0.5]][
                        cterm[
                          -opc[ctor[sports]],
                          -r[n[e1],w[0.5]][ind[explorer]],
                          -r[n[e2],w[0.5]][ind[escape]]
                        ]],
                      -r[n[year],w[0.3]][ind[1999]]
                    ]],
-r[n[summer],w[0.2]][
                      cterm[
                      -opc[ctor[auto]],
                      -r[n[make],w[0.8]][ind[ford]],
                      -r[n[model],w[0.1]][
                          cterm[
                            -opc[ctor[sedans]],
                            -r[n[e3],w[0.4]][ind[taurus]],
                            -r[n[e4],w[0.6]][ind[focus]]
                          ]],
                      -r[n[year],w[0.1]][ind[2000]]
                    ]]],
cterm[
-opc[ctor[vehicle]],
-r[n[autumn],w[0.3]][
                     cterm[
                     -opc[ctor[auto]],
                     -r[n[make],w[0.6]][ind[ford]],
                     -r[n[model],w[0.3]][
                          cterm[
                            -opc[ctor[sports]],
                            -r[n[e1],w[0.7]][ind[explorer]],
                            -r[n[e2],w[0.3]][ind[escape]]
                          ]],
                      -r[n[year],w[0.1]][ind[1999]]
                    ]],
-r[n[summer],w[0.7]][
                     cterm[
                     -opc[ctor[auto]],
                     -r[n[make],w[0.2]][ind[ford]],
                     -r[n[model],w[0.2]][ind[sports]],
                     -r[n[year],w[0.6]][ind[2001]]
                   ]]]
)

%adjust1: 0.9438
%adjust2: 0.9029
%adjust3: 0.8954
%adjust4: 0.8177
%adjust5: 0.7602