Comparing two algorithms that use differently the same functions

I have a set o rules and all the rules extract the same type of instances (names of cities for example) from a long text. I'm comparing the following two algorithms:

Algorithm1:

Algorithm2:

knowing that:

• each rule has the property "TP" which is the number of "correct extracted instances".
• The function sort(): sorts RulesList in decreasing order according to TP values.
• The function RemoveSubsumedRules() removes a rule R2 from RulesList if its "correct extracted instances" set is included the the one of a rule R1 (in RulesList).

is Algorithm1 the same as Algorithm2? they return the same RulesList (sames rules) in the end?

Or does Algorithm1 remove more rules than Algorithm2? (because RemoveSubsumedRules() is called in every iteration).

Thanks.

Both algorithms do the same thing (in terms of result produced).

To see this, we can prove that in the end, RuleList constsists of exactly those rules which are not subsumed by any other rule. In case of Algorithm 2 this is clear, so let us prove this for Algorithm 1.

First, it is easy to see that those rules are indeed in the final RuleList, as they cannot be deleted by RemoveSubsumedRules.

Secondly, suppose that there is some rule R1 in the final RuleList which is subsumed by some other rule R2 (not necessarily in the RuleList). Then there exists some rule R3 different than R1 which subsumes R1 and is not subsumed by any other rule (note that R3 might be equal to R2). We already know that R3 is in the final RuleList, because no other rule subsumes it. But in this case, when the last call to RemoveSubsumedRules was made, both R1 and R3 were in the RuleList, so R1 should have been removed, which we supposed wasn't the case. We have reached a contradiction, so no rule such as R1 can exist in the final RuleSet.