Computing Joins and Meets in Finite Lattices: Tight Instance-Sensitive Bounds, Output-Sensitive Enumeration, Bit-Parallel Speedups, and OML-Specific Accelerations

Computing Joins and Meets in Finite Lattices: Tight Instance-Sensitive Bounds, Output-Sensitive Enumeration, Bit-Parallel Speedups, and OML-Specific Accelerations Joaquim Reizi Higuchi November 19, 2025 Abstract We revisit the problem of computing joins and meets in finite lattices given by adjacency lists of their Hasse diagrams. Beyond the folklore Θ(n+m)worst-case bound, we establish four contributions. First, we prove instance-sensitive tight bounds: for any pair a, b, let U:=↑a∪ ↑ band write n[U] = |U|and m[U]for the number of cover edges induced by U. Then a∨b(dually a∧bwith D:=↓a∪ ↓b) can be computed in Θ(n[U]+m[U]) time via a two-source forward exploration that touches only U. We complement this with a matching adversarial lower bound in the adjacency-list access model, showing worst-case optimality when U=L(hence Θ(n+m)). Second, we extend to arbitrary finite posets: all minimal common upper bounds of aand b(witnessing non-existence of the join) can be enumerated in O(n[U] + m[U] + k)time, where kis the output size. Third, on a word-RAM with word size w= Θ(log n), after O(((n+m)n)/w)preprocessing and O(n2/w) space we answer join/meet queries in O(n/w +m[S]) time using bit-parallel operations, where S:=↑a∩ ↑ b(dually T:=↓a∩ ↓ b). Finally, when an orthomodular lattice (OML) is given with a Boolean block decomposition (Greechie-style pasting), block-local joins for commuting elements inside a common block can be computed in Θ(|B|+mB)time from adjacency lists, or in O(drB/we)time when an atom-incidence bit encoding is available (rB= log2|B|). These results refine the algorithmic landscape for lattice operations and pinpoint when OML-specific structure provides strict improvements. Keywords: orthomodular lattices, finite lattices, computational complexity, Hasse diagrams, output-sensitive algorithms, labeling and bit-parallel methods 1 Introduction Orthomodular lattices (OMLs) provide algebraic semantics for quantum logic [6, 20, 26]. From a computational viewpoint, basic operations such as joins and meets are ubiquitous in automated reasoning over finite quantum logics and in general lattice-based knowledge representation. A standard observation is that the join/meet of two elements 1 in a finite lattice can be computed in time linear in the size of the Hasse diagram by graph reachability. While correct, this statement masks two important refinements: (i) the explored region is much smaller than the whole lattice on many instances, and (ii) the same reachability machinery extends to non-lattices to enumerate minimal common upper bounds (witnessing non-existence of joins). This paper formalizes these refinements and adds two complementary accelerations: an adversarial lower bound that certifies optimality of the instance-sensitive upper bound, a word-RAM bit-parallel speedup for multi-query usage, and an OML-specific acceleration when a Boolean block decomposition is exposed. 1.1 Contributions Let Lbe a finite lattice (or OML) with Hasse diagram H(L) = (V, E),|V|=n,|E|=m. For a vertex subset X⊆V, write n[X] := |X|and m[X] := |{(u, v)∈E:u, v ∈X}| for the number of induced cover edges. •Tight instance-sensitive bounds. For a, b ∈Lset U:=↑a∪ ↑ band S:=↑ a∩ ↑ b. We prove that a∨bcan be computed in time Θ(n[U] + m[U]), with a symmetric statement for a∧busing D:=↓a∪ ↓b. The upper bound follows from a one-pass topological DP that explores only U; the lower bound uses an adversarial indistinguishability argument. •Output-sensitive enumeration in posets. For an arbitrary finite poset (not necessarily a lattice), we enumerate all minimal elements of S=↑a∩ ↑ bin time O(n[U] + m[U] + k)where kis the number of minimal common upper bounds. This yields a join existence test with explicit witnesses. •Bit-parallel speedup on word-RAM. With w= Θ(log n), a preprocessing in O(nm/w)time builds upward/downward reachability bitsets. Then each join/meet query is answered in O(n/w +m[S]) time via bitwise computation of Sfollowed by induced-edge filtering inside S. •OML-specific block acceleration. If an OML is given together with a Boolean block (Greechie) decomposition and the operands commute (belong to some common block), the join/meet is computed within that block in O(b)time where bis the block size; otherwise we fall back to the generic algorithm. This strictly improves the generic bounds when blocks are small. Relation to prior work. Classical texts on lattices emphasize structural properties [5, 9, 15]. The linear-time reachability approach is folklore in graph algorithms [7, 25]. Our novelties are the instance-sensitive tight bound with adversarial lower bound, the output-sensitive extension to arbitrary posets with explicit witnesses, a word-RAM quantification, and an OML-specific speedup under an explicit decomposition. 2 Preliminaries and Definitions We recall standard notions; see [5, 9, 15]. 2 Definition 2.1 (Posets and covers).Aposet is (L, ≤)with reflexive, antisymmetric, transitive ≤. We write y≺xif y < x and no zsatisfies y < z < x. Definition 2.2 (Hasse diagram).H(L) = (V, E)has V=Land E={(y, x) : y≺x} directed upward. Definition 2.3 (Lattices).Alattice is a poset where every pair has a join a∨band meet a∧b. A lattice is bounded if it has bottom 0and top 1. Definition 2.4 (Orthomodular lattices).An orthocomplemented bounded lattice (L, ≤ ,0,0,1) is orthomodular if a≤bimplies b=a∨(a0∧b). See [20]. Definition 2.5 (Upward/downward closures).↑x:= {y∈L:x≤y},↓x:= {y∈L: y≤x}. For S⊆L,s∈Sis minimal (maximal) in Sif no t∈Ssatisfies t < s (s < t). Input model and notation. We are given H(L)by adjacency lists (optionally both directions). For X⊆V,n[X] := |X|and m[X]counts cover edges with endpoints in X. We use a RAM model; basic operations cost O(1) [7]. 3 Warm-up: Order-Theoretic Characterizations and a One-Pass Algorithm Lemma 3.1 (Extremal characterization).In a lattice, a∨bis the unique minimal element of S:=↑a∩ ↑b, and a∧bis the unique maximal element of ↓a∩ ↓b. Proof. Let j:= a∨b. By the defining universal property of joins, a≤jand b≤j, and for every xwith a≤xand b≤xwe have j≤x. Hence j∈S. To show that jis minimal in S, let x∈Swith x≤j. Since x∈S, we have a≤xand b≤x, so by the universal property of jwe also have j≤x. Thus x≤jand j≤x, and by antisymmetry x=j. Therefore no element of Slies strictly below j, so jis minimal in S. To show uniqueness of the minimal element in S, let u∈Sbe minimal. Because uis a common upper bound of aand b, the universal property of jgives j≤u. Since j∈S and j≤u, the minimality of uforces u=j. Hence jis the unique minimal element of S. The meet case is dual. Let m:= a∧b. Then m∈T:=↓a∩ ↓ band, by the defining universal property of meets, for every xwith x≤aand x≤bwe have x≤m. If x∈T and m≤x, then x≤aand x≤b, hence x≤m; by antisymmetry x=m. Thus mis maximal in T. If v∈Tis maximal, then v≤aand v≤b, so v≤m; since m∈Tand v is maximal, we obtain v=m. Therefore mis the unique maximal element of T. Lemma 3.2 (Two-source upward exploration).Let Lbe a finite lattice with Hasse diagram H(L) = (V, E), edges oriented upward. Fix a, b ∈L. Define boolean marks reachA,reachB :V→ {0,1}and perform a forward search from the source set {a, b} along cover edges: initialize reachA[a] = reachB[b]=1and all other marks to 0; whenever we traverse an edge y→x, set reachA[x]←reachA[x]∨reachA[y],reachB[x]←reachB[x]∨reachB[y]. Let U:= {x∈V:reachA[x]∨reachB[x] = 1}, 3 S:= {x∈V:reachA[x]∧reachB[x] = 1}. Then: 1. For all x∈V,reachA[x] = 1 if and only if a≤x, and reachB[x] = 1 if and only if b≤x. In particular, U=↑a∪ ↑band S=↑a∩ ↑b. 2. Since Sis upward closed, x∈Sis minimal in Sif and only if there is no cover edge (y→x)∈Ewith y∈S. In a lattice, a∨bis the unique such element. 3. If out-neighbor adjacency lists are available, the forward search above and the minimality detection run in time On[U] + m+[U], m+[U] := {(y→x)∈E:y∈U}, using space O(n[U]). Dually, with in-neighbor lists one obtains O(n[U] + m−[U]) with m−[U] := |{(y→x)∈E:x∈U}|. Moreover, the topological DP reachA[x] = [x=a]∨_ y≺x reachA[y],reachB[x] = [x=b]∨_ y≺x reachB[y] is correct but takes O(n+m)time on the given adjacency lists. Proof. (1) Forward propagation preserves the property a≤ ·: if reachA[y]=1then a≤y, and y≺ximplies a≤x; conversely, in a finite poset a≤xiff there exists a saturated chain a=v0≺ · · · ≺ vk=x, along which the propagation sets all marks to 1. The statement for bis identical. (2) If x∈Sand z∈Swith z < x, take a saturated chain z=v0≺ · · · ≺ vr=x. Upward closedness of S(from a≤z≤viand b≤z≤vi) yields vr−1∈S, hence an incoming cover from S. The converse is immediate. Uniqueness of the minimal element in Sis the extremal characterization of joins. (3) Each y∈Uis extracted once; every out-edge (y→x)with y∈Uis examined once, so the search costs O(n[U] + m+[U]). Minimality is decided by one scan of the same edge set, marking xnon-minimal whenever y, x ∈S. The dual bound uses inneighbors. The topological DP is a correct alternative that inspects all in-edges of all x, hence O(n+m)time. 4 Main Result I: Tight Instance-Sensitive Bounds and Worst-Case Optimality Theorem 4.1 (Tight instance-sensitive bound for join).In a finite lattice with Hasse diagram H(L), for a, b ∈Llet U:=↑a∪ ↑band S:=↑a∩ ↑b. Then a∨bcan be computed in time Θ(n[U] + m[U]) and space O(n[U]) using adjacency lists restricted to U. Proof. Upper bound. Assume upward-oriented adjacency lists (out-neighbors along covers). Run the two-source forward exploration of Lemma 3.2: maintain boolean marks reachA,reachB :V→ {0,1} initialized by reachA[a] = 1,reachB[b] = 1, and propagate along each cover edge (y→x) by reachA[x]←reachA[x]∨reachA[y],reachB[x]←reachB[x]∨reachB[y], 4 pushing a vertex to the queue only when one of its marks flips from 0to 1. By Lemma 3.2(1), this yields U={x:reachA[x]∨reachB[x] = 1}=↑a∪ ↑b, S={x:reachA[x]∧reachB[x] = 1}=↑a∩ ↑b. By Lemma 3.2(3), the exploration touches exactly the vertices in Uand the out-edges of those vertices, hence runs in O(n[U] + m+[U]) time and O(n[U]) space. Since Uis an upper set (if y∈Uand y≺xthen x∈U), any out-edge (y→x)with y∈Ualso satisfies x∈U, so m+[U] = m[U]. Next, detect the unique minimal element of Susing only the edges induced by U (Lemma 3.2(2)): initialize isMinimal[x]=1for x∈Sand 0otherwise; then scan each induced edge (y→x)with y, x ∈Uonce and set isMinimal[x]←0whenever y, x ∈S. By Lemma 3.1, a∨bis the unique minimal element of S, so the (unique) x with isMinimal[x] = 1 is a∨b. This scan costs O(n[U] + m[U]) time and O(n[U]) space. Combining the exploration and the minimality scan, the total time is O(n[U] +m[U]) and the space is O(n[U]). Lower bound. In the adjacency-list access model, Theorem 4.3 shows that some instances force any correct algorithm to inspect Ω(n[U] + m[U]) adjacency entries. Thus the bound is tight and the running time is Θ(n[U] + m[U]). Theorem 4.2 (Tight instance-sensitive bound for meet).Let Lbe a finite lattice with Hasse diagram H(L) = (V, E). For a, b ∈L, define D:=↓a∪ ↓b, T :=↓a∩ ↓b. Then a∧bcan be computed in time Θ(n[D] + m[D]) and space O(n[D]) using the inneighbor adjacency lists of H(L)restricted to D(equivalently, the out-neighbor lists in the edge-reversed diagram Hrev(L)), where n[D]is the number of vertices in Dand m[D] is the number of cover edges in the subgraph induced by D. Proof. Upper bound. Work on the edge-reversed Hasse diagram Hrev(L), whose edges are x→yiff y→xin H(L). Run the two-source forward exploration of Lemma 3.2 from the source set {a, b}on Hrev(L), maintaining boolean marks reachA,reachB :V→ {0,1} that propagate along edges of Hrev(L)as in Lemma 3.2. By the dual of Lemma 3.2(1), this computes D={x:reachA[x]∨reachB[x] = 1}=↓a∪ ↓b, T={x:reachA[x]∧reachB[x] = 1}=↓a∩ ↓b. Moreover, the forward exploration in Hrev(L)touches exactly the vertices in Dand the out-edges of those vertices in Hrev(L), and hence runs in O(n[D] + m+ rev[D]) time and O(n[D]) space by Lemma 3.2(3). Since Dis a lower set in H(L), it is an upper set in Hrev(L); thus if (y→x)is an edge of Hrev(L)with y∈D, then also x∈D, and consequently m+ rev[D] = m[D]. Therefore the exploration costs O(n[D] + m[D]) time and O(n[D]) space. To identify a∧bas the unique maximal element of T, scan only edges of H(L)whose head lies in D(equivalently, scan in-neighbors in H(L)). Initialize isMaximal[x] = 1 for x∈Tand 0otherwise. For each edge (y→x)∈Ewith x∈D(and hence y∈D 5 by the lower-closedness of D), if y, x ∈Tthen set isMaximal[y]←0. Because Dis a lower set in H(L), the scanned family is exactly the set of edges induced by D, so this pass costs O(m[D]) time and O(n[D]) space. By Lemma 3.1, the (unique) x∈Twith isMaximal[x] = 1 is a∧b. A final linear scan over Dfinds this vertex in O(n[D]) time. Combining the two passes gives an O(n[D] + m[D])-time, O(n[D])-space algorithm. Lower bound. By the dual of Theorem 4.3 (or by the same adversarial indistinguishability argument applied to Dand T), any correct algorithm in the adjacency-list access model must inspect Ω(n[D] + m[D]) adjacency entries on some instances. Hence the bound is tight and the running time is Θ(n[D] + m[D]). Theorem 4.3 (Adversarial lower bound (adjacency-list access model)).Fix any algorithm Athat, given adjacency lists of the Hasse diagram H(L)and a, b ∈L, outputs a∨b. There are infinitely many pairs (n, m)for which there exists a family Fof finite lattices on nvertices and mcover edges, together with pairs (a, b), such that for some instance (L, a, b)∈ F algorithm Amust inspect Ω(n[U] + m[U]) adjacency entries to be correct, where U=↑a∪ ↑bin L. In particular, we can arrange U=L\ {B}(all vertices except the bottom), whence this yields a worst-case Ω(n+m)bound. Proof. We work in the adjacency-list access model: the algorithm learns the Hasse diagram only by requesting the out-neighbor list of a vertex and reading specific positions in that list; each such read counts as one inspected adjacency entry. A parameterized family. Fix an integer t≥1. For each index p∈ {1, . . . , t}we define a finite lattice Lpas follows. Vertices: V={B, a, b, T}∪{pi, qi, si: 1 ≤i≤t}. Intuitively, Bis bottom, Tis top; a, b are incomparable elements above B; for each column i,pilies just above a,qilies just above b, and siis a candidate common upper bound potentially lying strictly below T. Cover relation (Hasse edges) is defined by the following rules; after listing them we take the transitive reduction to obtain H(Lp). 1. B≺a,B≺b. 2. For each i,a≺piand b≺qi. 3. For each i,si≺T. 4. Switch edges per column. For i=p(the active column), include both pi≺siand qi≺si. For every i6=p(an inactive column), include exactly one of {pi≺si, qi≺ si}and omit the other; additionally, for the endpoint x∈ {pi, qi}where x≺siis omitted, include x≺Tso that x≤Tholds via a cover (while the other endpoint that does cover sidoes not cover Tbecause si≺Tsits in between). No further comparabilities among {pi, qi, si}iare added. Lattice property. It is routine to check that all binary joins and meets exist. Joins: Tserves as a fallback least upper bound; the only potential nontrivial join is pi∨qi, which equals siin the active column i=pand equals Tin inactive columns (since there siis not above both piand qiby construction). Meets: Bis a fallback greatest lower bound; otherwise meets are immediate along the covers introduced. Thus each Lpis a finite lattice with bottom Band top T. 6 The relevant region U.For every p, we have U=↑a∪ ↑b={a, b, T}∪{pi, qi, si: 1 ≤i≤t}. In particular B /∈Uand all other vertices do lie in U; hence |U|= 3t+ 3. Counting induced cover edges inside U: for each column iwe have a≺pi,b≺qi,si≺T, and, depending on the switch, one edge pi→(·)and one edge qi→(·), altogether 5edges per column. Thus m[U] = 5t+O(1). Consequently n[U] = Θ(t)and m[U] = Θ(t), so n[U] + m[U] = Θ(t). The join a∨b.In Lp, the set S:=↑a∩ ↑ bequals {T}∪{si:both pi≺siand qi≺ sihold}. By construction, this happens exactly for i=p, so S={sp, T}and the unique minimal element of Sis sp. Hence a∨b=spin Lp. Adversary strategy and lower bound. Consider any deterministic algorithm A. We expose the adjacency lists adaptively as follows. For each column i, the only entries of H(Lp)that determine whether si∈Sare the two switch entries for the covers pi≺siand qi≺si. Moreover, by the way we defined covers to T, the out-degree of each of pi, qiequals 1in H(Lp): either it points to si(when the corresponding switch is present) or it points to T(when that switch is absent). Thus, to learn whether the switch at pi(resp. qi) is present, Amust actually read the unique neighbor of pi(resp. qi) from the adjacency list—one inspected entry per endpoint. We maintain the invariant that, until we commit to some active index p, every column iremains ambiguous unless Ahas already read both switch endpoints for that column and discovered that at least one of them points to T. Concretely, whenever Ais the first to read a switch endpoint of column i, we answer so that this endpoint points to si (keeping the column ambiguous); only when Areads the second endpoint of an inactive column i6=pdo we answer that this second endpoint points to T(thereby resolving column ias inactive). We defer the choice of pand guarantee that, for whichever column survives longest as ambiguous, both of its endpoints will point to si, making it the active one. Under this strategy, Acannot terminate with a correct output as long as there are at least two ambiguous columns, since the transcript so far would be consistent with two different instances Lpproducing two different joins sp. Therefore, before termination, all but at most one column must have been resolved as inactive, and for each such column the adversary has forced Ato read both switch endpoints in order to see one pointing to T. It follows that Ainspects at least 2(t−1) adjacency entries within U. Hence, for some instance in the family {Lp}t p=1, the number of inspected entries is Ω(t) = Ω(n[U]+m[U]). Worst-case bound when U=L.In the above construction, every vertex except B lies above aor b, so U=L\ {B}. This implies n[U] = n−1and m[U] = m−O(1); therefore the lower bound becomes Ω(n+m). Since tis arbitrary, this yields the claim for infinitely many (n, m). Remark 4.4 (Discussion).Theorems 4.1, 4.2, and 4.3 sharpen the folklore O(n+m) bound. They certify optimality of exploring only the portion of the Hasse diagram that is relevant to aor b. 7 5 Main Result II: Output-Sensitive Enumeration in Arbitrary Posets We now drop the lattice assumption. Theorem 5.1 (Output-sensitive enumeration of minimal common upper bounds).Let (P, ≤)be a finite poset with Hasse diagram H(P) = (V, E), edges oriented upward along the cover relation, and let a, b ∈P. For x∈Pwrite ↑x:= {y∈P:x≤y}, and set U:=↑a∪ ↑ band S:=↑a∩ ↑ b. Let n[U] := |U|and let m[U]be the number of cover edges in the subgraph of H(P)induced by U. Assuming out-neighbor adjacency lists are given, there is an algorithm that enumerates all minimal elements of Sin time O(n[U] + m[U] + k)and space O(n[U]), where kis the number of minimal elements of S. (The dual statement with in-neighbor lists is analogous.) Proof. We give an algorithm that touches only the vertices of Uand the edges induced by U. Step 1: compute Uand Sby two-source forward exploration. Run the twosource forward exploration (as in Lemma 3.2) from sources {a, b}along upward cover edges. Maintain boolean marks reachA,reachB :V→ {0,1}that propagate on each edge y→xby reachA[x]←reachA[x]∨reachA[y],reachB[x]←reachB[x]∨reachB[y], pushing a vertex when a mark flips to 1. Then U={x:reachA[x]∨reachB[x] = 1}=↑a∪ ↑b, S={x:reachA[x]∧reachB[x] = 1}=↑a∩ ↑b. Because Uis an upper set, every out-edge (y→x)with y∈Ualso satisfies x∈U; hence this exploration touches exactly the n[U]vertices in Uand the m[U]induced edges, and runs in O(n[U] + m[U]) time using O(n[U]) space. Step 2: detect minimal elements of Sby a single induced-edge scan. Initialize isMinimal[x] = 1 for x∈Sand 0otherwise. Scan each cover edge (y→x)with y, x ∈U exactly once; if y∈Sand x∈S, set isMinimal[x]←0. We claim that at the end, isMinimal[x] = 1 ⇐⇒ x∈Sand xis minimal in S. “⇒”: Suppose isMinimal[x]=1but xis not minimal in S. Then there exists z∈S with z < x. Choose a saturated chain z=v0≺v1≺ · · · ≺ vr=x. Since z∈Sand Sis an upper set, we have vi∈Sfor all i; in particular, the cover edge (vr−1→x)has both endpoints in S, and the scan would set isMinimal[x] = 0, a contradiction. “⇐”: If x∈Sis minimal, then no cover predecessor yof xlies in S, so the scan never resets isMinimal[x]; hence it remains 1. Step 3: enumeration and complexity. Output all x∈Uwith isMinimal[x] = 1. Step 1 costs O(n[U] + m[U]) time and O(n[U]) space; Step 2 costs O(m[U]) time and O(n[U]) space; the final sweep to emit all minima takes O(n[U] + k)time. Therefore the total running time is O(n[U] + m[U] + k)and the space is O(n[U]). Corollary 5.2 (Join existence with witnesses).If Shas exactly one minimal element u, then u=a∨bin the lattice-theoretic sense; if Shas at least two incomparable minima, the poset is not a lattice on {a, b}and these minima are explicit witnesses of non-existence of a∨b. 8 6 Main Result III: Bit-Parallel Speedups on the WordRAM We quantify improvements under a standard word-RAM model with w= Θ(log n). Theorem 6.1 (Bit-parallel preprocessing and query bounds).Assume a word-RAM with word size w= Θ(log n). Let Lbe a finite lattice with Hasse diagram H(L)=(V, E), |V|=n,|E|=m. There is a preprocessing algorithm that, in O(((n+m)n)/w)time and O(n2/w)space, builds for each x∈Ltwo bitsets Up[x],Down[x]∈ {0,1}n encoding the upward and downward closures: Up[x](y) = 1 ⇐⇒ x≤y, Down[x](y) = 1 ⇐⇒ y≤x. After preprocessing, a join query a∨bcan be answered as follows: 1. Compute S:= Up[a] & Up[b]in O(n/w)time. 2. Initialize a bitset NotMin := 0. For each ywith S(y) = 1, scan the out-neighbors of y; for every cover edge (y→x)∈Eset NotMin(x) := 1. Since S:=↑a∩ ↑bis an upper set, every such xalso lies in S, and exactly the m[S]edges induced by S are examined. This step costs O(m[S]). 3. Compute Min := S&¬NotMin and return the unique xwith Min(x) = 1 (when Lis a lattice); finding this set bit takes O(n/w)time. Meet queries are answered symmetrically: compute T:= Down[a] & Down[b], then for each xwith T(x)=1scan the in-neighbors of xand mark those ywith (y→x)∈E as non-maximal; since T:=↓a∩ ↓ bis a lower set, this inspects exactly m[T]edges. Therefore, after preprocessing, each join (resp. meet) query runs in time O(n/w +m[S]) (resp. O(n/w +m[T])), using O(n2/w)space overall for the bitsets. Proof. We first describe how to construct the bitsets Up[x]and Down[x], then the query procedures and their costs. Bitset representation. Fix an enumeration V={v1, . . . , vn}. Every subset X⊆V is represented by a bit vector X∈ {0,1}nstored in dn/wemachine words. Bitwise OR/AND/NOT and membership tests take O(n/w)time per operation. Preprocessing for upward closures. Compute a topological order π= (v1, . . . , vn) of H(L)in O(n+m)time. Process vertices in reverse topological order vn, . . . , v1and maintain Up[x]as follows: initialize Up[x]to the zero vector; set Up[x](x) := 1; for each outgoing cover edge (x→z)∈E, update Up[x]←Up[x]∪Up[z]. An induction along the reverse order shows Up[x](y) = 1 ⇐⇒ x≤y. Preprocessing for downward closures. Process vertices in the forward order π. Initialize Down[x]to zero and set Down[x](x) := 1; for each incoming cover edge (y→ x)∈E, update Down[x]←Down[x]∪Down[y]. 9