Morgan Acceptance Heuristic

Overview

The Morgan heuristic, proposed by Davila, filters conjectures based on the generality of the hypothesis. It ensures that only the most general form of a conjecture is retained for each logical conclusion.

This heuristic rejects redundant conjectures whose hypotheses are strict subsets of already accepted ones with the same inequality conclusion.

Acceptance Criteria

A candidate conjecture \(C = H \Rightarrow (LHS \leq RHS)\) is accepted if:

  • There does not exist any previously accepted conjecture with: - The same logical conclusion (possibly in flipped form), and - A strictly more general hypothesis (i.e., a hypothesis that covers more rows in the dataset than H).

If such a more general conjecture exists, the new one is rejected.

Function Signature

txgraffiti.heuristics.davila.morgan_accept(new_conj, existing, df)[source]

Accept new_conj only if no existing conjecture with the same logical conclusion has a hypothesis mask that strictly contains new_conj’s mask.

In other words, we reject new_conj if there is already a strictly more general conjecture (same bound but wider hypothesis coverage).

Parameters:

  • new_conj (Conjecture) – The candidate conjecture to test.

  • existing (list of Conjecture) – Previously accepted conjectures to compare against.

  • df (pandas.DataFrame or KnowledgeTable) – The data table on which to evaluate hypothesis masks.

Returns:

True if no strictly more general existing conjecture was found, False otherwise.

Return type:

bool

Examples

>>> import pandas as pd
>>> from txgraffiti.logic import Predicate, Property, Conjecture, Inequality
>>> from txgraffiti.heuristics.davila import morgan_accept
>>> df = pd.DataFrame({
...     'alpha':     [1, 2, 3],
...     'beta':      [3, 2, 1],
...     'connected': [True, True, True],
...     'tree':      [False, True, False],
... })
>>> P_gen  = Predicate('connected', lambda df: df['connected'])
>>> P_sub  = Predicate('tree',      lambda df: df['tree'])
>>> A = Property('alpha', lambda df: df['alpha'])
>>> B = Property('beta',  lambda df: df['beta'])
>>> # less general hypothesis on tree
>>> c1 = P_sub >> (A <= B)
>>> # more general hypothesis on connected
>>> c2 = P_gen >> (A <= B)
>>> # c2 covers strictly more rows → accept c2 but not c1 if c2 exists
>>> morgan_accept(c1, [c2], df)
False
>>> morgan_accept(c2, [c1], df)
True

Notes

  • This heuristic relies on the helper function same_conclusion() to compare bounds up to logical equivalence.

  • Hypotheses are compared using boolean masks on the dataset to determine strict containment.

See Also