Chapter 2. Lattice-Linear Predicate Detection

A finite distributive lattice, a lattice-linear predicate, and a single algorithm that drives much of the rest of the book.

The framework

The LLP algorithm searches a finite distributive lattice $L$ for the least element that satisfies a Boolean predicate $B$. A predicate is lattice-linear if, whenever $B(G)$ is false, at least one component $j$ of the current vector $G$ is forbidden: any larger vector $H \geq G$ with $H[j] = G[j]$ also fails $B$. The algorithm advances any forbidden component to the smallest value consistent with $B$ and repeats:

while ∃ j : forbidden(G, j):
    G[j] := smallest value that resolves the violation
return G

Three pieces are required for an LLP problem: a lattice $L$, a predicate $B$, and an advance rule. The demos below show several small concrete instances.

LLP-GCD

Compute the greatest common divisor of an array of positive integers. The lattice is $\{1, 2, \ldots, \max\}^n$ with the usual componentwise order; the predicate is “all components are equal.” The advance rule reduces a forbidden component by modulo with a smaller component.

Time complexity: $O(n \log \max_i A[i])$ — each component reaches the gcd in $O(\log)$ Euclidean-mod steps.

LLP-EuclidGCD

The 2-element specialisation of LLP-GCD; on a length-2 input it is exactly classical Euclid by repeated subtraction, but written in the LLP shape so the connection to LLP-GCD is visible.

Time complexity: $O(\max(a, b))$ via repeated subtraction; the standard mod-based variant achieves $O(\log \min(a, b))$.

LLP-JobScheduling-Forbidden

Minimum completion time per job given prerequisites $\text{pre}(j)$. The advance may fire repeatedly on the same $j$ if its predecessors keep changing.

Time complexity: $O(nm)$, where $n$ is the number of jobs and $m$ the number of precedence edges.

LLP-JobScheduling-Ensure

The same algorithm using the ensure (j) : LHS >= RHS sugar — the LL compiler desugars to the equivalent forbidden/advance pair.

Time complexity: $O(nm)$, where $n$ is the number of jobs and $m$ the number of precedence edges.

LLP-JobScheduling-Fixed

An efficient reformulation: each job is advanced at most once, gated by a side flag fixed[j] that becomes true once all of $j$'s predecessors are finalised. The same pattern reappears in LLP-Layering.

Time complexity: $O(n + m)$ (Kahn-style topological sweep), where $n$ is the number of jobs and $m$ the number of precedence edges.

LLP predicates for this chapter

Each LLP program in this chapter defines a state vector $G$ and a forbidden predicate; the algorithm runs until no $j$ is forbidden. The table below lists, for each algorithm, what $G[i]$ represents and the negation of the forbidden clause from the matching .llp source.

Looking ahead

Every algorithm chapter from Chapter 4 onwards recasts a classical algorithm in this framework: stable matching (Gale-Shapley), sorting (LLP-Sort), graph traversal (LLP-BFS), greedy algorithms, shortest paths, minimum spanning trees, dynamic programming, and network flow.