Dalmatian Acceptance Heuristic

Overview

The Dalmatian heuristic, introduced by Fajtlowicz, provides a principled filter for deciding whether a newly proposed upper-bound conjecture should be accepted, based on validity and strict improvement over existing bounds.

It is named for the “spotted” pattern of truth: accepted conjectures must cover all points (no false spots) while improving at least one (showing a distinct spot of significance).

Acceptance Criteria

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

  1. (Truth Test) The inequality holds for all objects satisfying the hypothesis H.

  2. (Significance Test) There exists at least one object for which the new RHS is strictly tighter (i.e., strictly less) than every previously accepted RHS bound with the same hypothesis and left-hand side.

If no matching prior bounds exist, the candidate is accepted by default.

Function Signature

txgraffiti.heuristics.fajtlowicz.dalmatian_accept(new_conj, existing, df)[source]

Determine whether to accept a new upper‐bound conjecture based on the Dalmatian heuristic.

The Dalmatian heuristic accepts new_conj if and only if:

  1. It is valid on all rows under its hypothesis.

  2. Its right‐hand side (RHS) is strictly smaller on at least one row compared to the minimum RHS of all existing upper‐bounds with the same hypothesis and same conclusion LHS.

Parameters:

  • new_conj (Conjecture) – Candidate conjecture of the form H → (lhs ≤ rhs).

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

  • df (pandas.DataFrame or KnowledgeTable) – Tabular data on which to evaluate hypotheses and RHS values.

Returns:

True if new_conj is globally valid and strictly tighter than every matching existing bound; False otherwise.

Return type:

bool

Examples

>>> import pandas as pd
>>> from txgraffiti.logic import Property, Predicate, Conjecture, Inequality
>>> from txgraffiti.heuristics.fajtlowicz import dalmatian_accept
>>> df = pd.DataFrame({
...     'alpha':     [1, 1, 1],
...     'beta':      [1, 1, 1],
...     'connected': [True, True, True],
... })
>>> P = Predicate('connected', lambda df: df['connected'])
>>> A = Property('alpha', lambda df: df['alpha'])
>>> B = Property('beta',  lambda df: df['beta'])
>>> weak   = P >> (A <= B + 2)
>>> strong = P >> (A <= B + 1)
>>> best   = P >> (A <= B)
>>> # No existing bounds ⇒ accept
>>> dalmatian_accept(best, [], df)
True
>>> # Reject the weaker conjecture
>>> dalmatian_accept(weak, [strong], df)
False
>>> # Accept the strictly tighter one
>>> dalmatian_accept(best, [strong], df)
True