⇶ GMeetMono

GMeet algorithms

October 2022.
This document presents the implementation and tests of GMeetStar, GMeetMonoStar, GMeetMonoLazy and GMeetPlus.
Paper experiments:
Lattice sizes: [1,2,5,10,20,50,100,200,500]
Lattices per size: 12 (whenever possible)
Test functions per lattice: 500
Time limit: 1000 μ\mus


nnGMeetStarGMeetMonoStarGMeetMonoLazyGMeetPlusDMeetPlus
nnGMeetStarGMeetMonoStarGMeetMonoLazyGMeetPlusDMeetPlus
nnGMeetStarGMeetMonoStarGMeetMonoLazyGMeetPlusDMeetPlus
nnGMeetStarGMeetMonoStarGMeetMonoLazyGMeetPlusDMeetPlus
Playground:
Choose a lattice:

Number of elements: 8
Seed for presets: (re-click on a preset to apply)

(Running on the chosen lattice of 8 elements)

Algorithms:
Type of input function:

Notation

Throughout this document we use the following notation. LL is a non-empty finite lattice with order \sqleq and join and meet operators ,\join, \meet. The bottom element of LL is \bot. The set of all endomorphisms (functions f:LLf:L\to L) is denoted as F\calF, and it is a lattice with the order fFg    (xL) f(x)g(x). f \sqleqF g \iff (\forall x\in L)\ f(x)\sqleq g(x). The join and meet operators in F\calF (i.e. F\joinF and F\meetF) are the pointwise join and meet operators in LL. The endomorphisms that preserve least upper bounds and map \bot to \bot are called join-endomorphisms, and EF\calE\subseteq\calF is the set of all join-endomorphisms, that is,Edef{f:LLf()=(a,bL)f(ab)=f(a)f(b)}. \calE\eqdef\set{f:L\to L \given f(\bot)=\bot \,\wedge\, \lr{\forall a,b\in L}\,f(a\join b)= f(a)\join f(b)}. The order E\sqleqE for E\calE is defined as the restriction of F\sqleqF to E\calE, and with this order, E\calE is also a lattice. The join operator E\joinE coincides with F\joinF (pointwise \join), but the meet F\meetF does not coincide with F\meetF.

Algorithms of reference

All the algorithms presented compute the maximal join-endomorphism below a given endomorphism.
The implementations are based on the following abstract algorithms that do not indicate how to find the pairs a,ba,b.
GMeet(h)\mathtt{GMeet}(h):
while a,bL\exists a,b\in L with h(ab)h(a)h(b)h(a\join b) \neq h(a)\join h(b):
if h(ab)h(a)h(b)h(a\join b) \sqgt h(a) \join h(b):
h(ab)h(a)h(b)h(a\join b) \leftarrow h(a) \join h(b)
else:
h(a)h(a)h(ab)h(a) \leftarrow h(a) \meet h(a\join b)
h(b)h(b)h(ab)h(b) \leftarrow h(b) \meet h(a\join b)
return hh
GMeet algorithm. GMeet(fFg)deffEg\mathtt{GMeet}(f \meetF g) \eqdef f \meetE g.
GMeetMono(f,g)\mathtt{GMeetMono}(f, g):
hdeffFgh \eqdef f \meetF g
while a,bL\exists a,b\in L with h(ab)h(a)h(b)h(a\join b) \neq h(a)\join h(b):
if h(ab)h(a)h(b)h(a\join b) \sqgt h(a) \join h(b):
c=h(a)h(b)c = h(a) \join h(b)
for each xabx \sqleq a\join b
h(x)h(x)ch(x) \leftarrow h(x) \meet c
return hh
GMeetMono algorithm. GMeetMono(fFg)deffEg\mathtt{GMeetMono}(f \meetF g) \eqdef f \meetE g.

Implementations

Notation following variables that are used in the algorithms are present in the lattice L and are assumed to be precomputed:
Notation: n is the number of nodes in the lattice. m is the number of edges in the Hasse diagram of the lattice. lub[a][b] is the join (least upper bound) of a and b. glb[a][b] is the meet (greatest lower bound). leq[a][b] is the boolean for aba \sqleq b. geq[a][b] is the boolean for aba \sqgeq b. lt[a][b] is the boolean for aba \sqlt b. gt[a][b] is the boolean for aba \sqgt b. children[b] is the list of (direct) children of bb. parents[a] is the list of (direct) parents of aa.
The implementation of the algorithms, including the counters is shown below.

See the full code.