Chapter 3. Lattice-Linear Language

A small surface language for composing LLP programs.

Stub page. Interactive demos for the composition operators are planned for a future site update. The present page summarises the chapter's content for navigational purposes.

Overview

LLP programs are usually presented one at a time, each with its own state vector $G$, forbidden predicate, and advance rule. In practice, larger algorithms are built by composing several LLP programs that share a state. This chapter introduces a small surface language for expressing such compositions cleanly. Seven composition operators are defined:

• Sequencing $P_1\,;\,P_2$ — run $P_1$ to its fixpoint, then $P_2$ starting from $P_1$'s output.
• Parallel composition $P_1\,[]\,P_2$ — run $P_1$ and $P_2$ concurrently on the same state, dispatching each forbidden index to its owning program.
• Nondeterministic choice $P_1\,\mathbf{or}\,P_2$ — pick one of the two programs and run it (used when multiple LLP formulations exist for the same problem).
• Pipelining $P_1\,|\,P_2$ — $P_2$ consumes the output of $P_1$ as it is produced.
• Predicate conjunction $P_1\,\&\&\,P_2$ — strengthen the feasibility predicate of $P_1$ with that of $P_2$. This is the operator used to compose a constraint program onto a base algorithm (e.g.\ {Constrained Shortest Path}, {Constrained MST}, {Constrained Greedy}).
• Synchronous composition $P_1\,\mathbf{sync}\,P_2$ — both programs advance in lockstep at every forbidden index.
• Feedback composition $P_1\,\langle\rangle\,P_2$ — the output of one program feeds back into the input of the other until a joint fixpoint is reached.

For each operator, the chapter states conditions under which the composition preserves lattice-linearity, and illustrates the operator with a concrete example drawn from later chapters (stable marriage, shortest path, MST).

Related material on this site

Several later chapters use compositions defined here:

• Chapter 7 (Greedy Algorithms) — Constrained Greedy as $[\,\textsf{LLP-Greedy}\,\&\&\,\textsf{Constraint}\,]$.
• Chapter 8 (Shortest Path) — Constrained Shortest Path with hop-budget and resource-budget rules composed onto LLP-Dijkstra.
• Chapter 9 (Minimum Spanning Tree) — Constrained MST with mandatory edges composed onto LLP-Kruskal.
• Chapter 12 (Network Flow) — Constrained mincut as a 1-transition LLP composed onto the cut lattice.