and 3 contributors

# NAME

Algorithm::AM::lattice - How to store and manipulate large lattices in C

version 3.12

# DESCRIPTION

The Analogical Modeling (AM) algorithm requires constructing and traversing large completely distributive lattices, also known as Boolean algebras. This document tells how we do it in Parallel.xs.

A lot of what appears below could be used generally to store lattices; that which applies specifically to `AM::Parallel` is so marked.

# BOOLEAN ALGEBRAS AND LATTICES

If n is a positive integer, then the set of positive integers that can be expressed in n or fewer bits, along with the operations & (bitwise AND) and | (bitwise OR), is an example of a Boolean algebra. It is also an example of a lattice which is completely distributive. Although all the lattices used in AM are in fact Boolean algebras, it is customary to refer to them merely as lattices.

Any lattice can have a partial order imposed upon it; this is done by defining a <= b whenever a & b = b (or equivalently, a | b = a). This partial order is symmetric, transitive, and antireflexive (if a <= b and b <= a, then a = b). It's called a partial order because it is often the case that neither a <= b nor b <= a.

A common way to draw lattices on paper is by putting elements that are greater than other elements higher up on the paper, using line segments to indicate the partial order. Here's an example:

``````                000
/|\
/ | \
/  |  \
/   |   \
001  010  100
| \  / \  / |
|  \/   \/  |
|  /\   /\  |
| /  \ /  \ |
011  101  110
\   |   /
\  |  /
\ | /
\|/
111``````

If you can get from one element to another by only going down along the line segments, then the first element is greater than the second.