Modeling Abstraction — α and γ

We now have two representations:

• The concrete powerset lattice 𝒫(Loc → N) — precise but expensive.
• The abstract lattice of partial assignments — cheap but lossy.

We connect them with a pair of functions:

α (abstraction)

Given a set of complete grids, extract the facts they all agree on. We say α(S) abstracts S.

γ (concretization)

Given a partial assignment, return every complete grid compatible with it. We say γ(a) is what a represents.

We use these barbed half-arrows to denote the relationship between the two lattices — a notation we'll return to.

Formally, for our Sudoku domain:

That is, α extracts every cell assignment that all grids in the set agree on.

And γ returns every complete grid that is compatible with the partial assignment.

For example, take two complete grids that agree on their upper half:

The two grids agree on rows 1 and 2 but differ on rows 3 and 4 — so α keeps only the first eight facts. Applying γ(α(S)) would return all 4⁸ = 65,536 complete grids that match those eight cells — including invalid ones.