17
$\begingroup$

Wikipedia says:

Complete lattices appear in many applications in mathematics and computer science

Is it just referring to the fact that the standard Boolean algebra used in computation is a complete lattice? Is there anything we gain by working at the abstract level of lattices instead of with Boolean logic specifically?

A google search doesn't find much on the subject, but I'm probably using the wrong keywords.

$\endgroup$
1
12
$\begingroup$

See for instance this book: Lattice Theory with Applications, Vijay K. Garg, which starts off as follows:

Partial order and lattice theory now play an important role in many disciplines of computer science and engineering. For example, they have applications in distributed computing (vector clocks, global predicate detection), concurrency theory (pomsets, occurrence nets), programming language semantics (fixed-point semantics), and data mining (concept analysis). They are also useful in other disciplines of mathematics such as combinatorics, number theory and group theory. In this book, I introduce important results in partial order theory along with their applications in computer science. The bias of the book is on computational aspects of lattice theory (algorithms) and on applications (esp. distributed systems).

The book doesn't seem to mention recursion theory (theory of computable sets), but from Wikipedia's article on Computability theory, we see:

When Post defined the notion of a simple set as an r.e. set with an infinite complement not containing any infinite r.e. set, he started to study the structure of the recursively enumerable sets under inclusion. This lattice became a well-studied structure. Recursive sets can be defined in this structure by the basic result that a set is recursive if and only if the set and its complement are both recursively enumerable. Infinite r.e. sets have always infinite recursive subsets; but on the other hand, simple sets exist but do not have a coinfinite recursive superset. Post (1944) introduced already hypersimple and hyperhypersimple sets; later maximal sets were constructed which are r.e. sets such that every r.e. superset is either a finite variant of the given maximal set or is co-finite. Post's original motivation in the study of this lattice was to find a structural notion such that every set which satisfies this property is neither in the Turing degree of the recursive sets nor in the Turing degree of the halting problem. Post did not find such a property and the solution to his problem applied priority methods instead; Harrington and Soare (1991) found eventually such a property.

Further reading, see the blog post Lattice Theory for Programmers and Non Computer Scientists.

$\endgroup$
2
  • 2
    $\begingroup$ Let me just add to this that lattices, and the related notion of domain, are used heavily in semantics of programming languages. $\endgroup$ – Andrej Bauer Jun 18 '13 at 10:27
  • $\begingroup$ @AndrejBauer could you give some pointers to examples? Thanks. $\endgroup$ – moleike Nov 11 '19 at 9:47
4
$\begingroup$

I have since found the free paper Ordered Sets and Complete Lattices: A Primer for Computer Science, for other interested readers.

$\endgroup$
3
$\begingroup$

Regular edge labelings and related structures form a distributive lattice (see for example here). This can be exploited to search efficiently through the space of all regular edge labelings for a given graph (see here) . As an application you can determine if a map can be drawn as cartogram with a certain area assignment for the faces.

$\endgroup$
3
$\begingroup$

The references given by Pål GD are indeed very appropriate. So let's focus on a minor side issue in this answer instead. I have done some reading on lattices some time ago, and started to wonder whether the notion of semilattice wouldn't have been more appropriate for applications. You might object that a complete semi-lattice is automatically also a lattice, but the homomorphisms and substructures (i.e. sublattices and subsemilattices) are different.

I first encountered (semi-)lattices when studying semigroups, as the commutative idempotent semigroups. Then I thought about the relation between hierarchic structures and lattices, and noticed that a tree is naturally also a semilattice. Then I found lattices in security contexts and in program analysis, and always it seemed to me like the semilattice structure was the really important part, and the lattice was just taken because it could be obtained "for free". Even for a Heyting algebra, there is an asymmetry between conjunction and disjunction which suggests to me that the asymmetric semilattice model might provide more insight here than the symmetric lattice model.

$\endgroup$
2
  • 1
    $\begingroup$ Can you elaborate on how trees are semilattices? And especially if there are any interesting theorems we can prove about data structures by using (semi-)lattices? $\endgroup$ – Xodarap Jun 20 '13 at 13:40
  • $\begingroup$ @Xodarap If we regard a tree as a partial ordered set, the join of two nodes is given by their lowest common ancestor. Regarding your request about data structures, I guess this is related to my earlier question about data structure for semilattices. My conclusion at the time was that it is a surprisingly non-trivial problem. Also, I had little intention to wander too far off from the mainstream, so I was quite happy to find that blogpost with the great reference section. $\endgroup$ – Thomas Klimpel Jun 21 '13 at 8:14
3
$\begingroup$

a very important, but not-so-famous case—it is well known among theorists but not so well known in the sense of being taught to undergraduates—of the use of a lattice is to prove superpolynomial lower bounds on the size of monotone circuits computing Clique for which Razborov won the Nevanlinna prize. the original construction is very technical however and later constructions eg Berg/Ulfberg simplify the framework without the reference to lattices.

so in this case lattice theory was used as a framework to discover the original proof but later formulations tended to not refer to it directly as a conceptual simplification.

so yes lattices may be regarded as a more exotic mathematical object [Razborov has spoken elsewhere of his style of applying advanced mathematics to CS] that might correspond to some other more "concrete" object in CS, in this case it is "approximation gates" ie boolean gates in circuits that give "approximately correct" answers and which the lattice is a sort of "induction structure" for converting between an exact circuit to an inexact, approximate circuit.

$\endgroup$
2
$\begingroup$

Also, surprisingly (for me, at least) cryptography. Check it out, it allows new attacks of known cryptosystems and gives hopes for post-quantum-computing cryptography.

$\endgroup$
3
  • 2
    $\begingroup$ This kind of "periodic" lattice is not the same as the OP is asking about. The question is about structures with binary operations meet and join. $\endgroup$ – András Salamon Jun 18 '13 at 9:24
  • $\begingroup$ Oops. Then I didn't get at all what was the OP asking about. $\endgroup$ – Helios Jun 18 '13 at 9:27
  • $\begingroup$ But the lattices Helios is talking about are in fact distributive lattices in the usual dominance order. Also, and I may be wrong, but I think any distributive lattice can be embedded in space as a subset of a periodic lattice. And they are arguably the most exciting thing in cryptography right now. $\endgroup$ – Sasho Nikolov Jul 1 '13 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.