Package it.unimi.dsi.lama4j

Interface Lattice

All Known Implementing Classes:
AbstractDistributiveLattice, AbstractLattice, Boolean, Chain, Flat, IntervalAntichains, Op, Parts, Product, Sum, Trivial
public interface Lattice
A lattice with zero and one (sometimes called a bounded lattice). This is equivalent to a partial order with all finite sups and infs.

The method isDistributive() can be used to discover whether distributivity holds.

  • Field Summary

    Fields 
    Modifier and Type Field Description
    static boolean RING
    Use ring notation (+ and * instead of | and &) in all output.
    static boolean UTF8
    Use UTF-8 symbols for operators in all outputs.

  • Method Summary

    Modifier and Type Method Description
    boolean comp​(Element x, Element y)
    Return whether the two provided elements are comparable.
    Map<Element,​Set<Element>> coveringRelation()
    Return the covering relation of this lattice.
    Collection<Element> elements()
    Return all elements of this lattice (optional operation).
    Collection<Element> generators()
    Return a collection of generators for the lattice.
    boolean isDistributive()
    Return true if this lattice is distributive.
    Element join​(Element... element)
    Return the join of the provided elements.
    boolean leq​(Element x, Element y)
    Return whether an element is less than or equal to another element in the natural order of this lattice.
    Element meet​(Element... element)
    Return the meet of the provided elements.
    Element one()
    Return the one of this lattice.
    Element pscomp​(Element x, Element y)
    Return the pseudocomplement of the first element relative to the second element (optional operation).
    Element psdiff​(Element x, Element y)
    Return the Brouwerian pseudo-difference of two elements (optional operation).
    Element symdiff​(Element x, Element y)
    Return the symmetric difference of the arguments, that is, psdiff(x,y).join(psdiff(y,x)).
    Element valueOf​(String name)
    Return an element of this lattice, given its name.
    Element zero()
    Return the zero of this lattice.

  • Field Details

    • UTF8

      static final boolean UTF8
      Use UTF-8 symbols for operators in all outputs. This constant is settable using the Boolean system property it.unimi.dsi.lama4j.utf8.

    • RING

      static final boolean RING
      Use ring notation (+ and * instead of | and &) in all output. This constant is settable using the Boolean system property it.unimi.dsi.lama4j.ring.

  • Method Details

    • isDistributive

      boolean isDistributive()
      Return true if this lattice is distributive.
      Returns:
      true if this lattice is distributive.

    • meet

      Element meet​(Element... element)
      Return the meet of the provided elements. In particular, upon the empty list of arguments returns one, and upon a singleton list the only specified element.
      Parameters:
      element - the elements whose meet has to be computed.
      Returns:
      the meet of the provided elements.

    • join

      Element join​(Element... element)
      Return the join of the provided elements. In particular, upon the empty list of arguments returns zero, and upon a singleton list the only specified element.
      Parameters:
      element - the elements whose join has to be computed.
      Returns:
      the join of the provided elements.

    • generators

      Collection<Element> generators()
      Return a collection of generators for the lattice. The set will not include zero or one. There is no guarantee of freeness or minimality.
      Returns:
      a collection of generators.

    • elements

      Collection<Element> elements()
      Return all elements of this lattice (optional operation).

      This operation might not implemented, for instance, in infinite lattices.

      Returns:
      the collection of all elements of this lattice.

    • valueOf

      Element valueOf​(String name)
      Return an element of this lattice, given its name.

      Certain lattices make it possible to define names for elements. This method returns the element corresponding to the provided name.

      Parameters:
      name - the name of an element of this lattice.
      Returns:
      the element of this lattice named name.
      Throws:
      ElementNameException - if the provided name does not match any element of this lattice.

    • zero

      Element zero()
      Return the zero of this lattice.

      Note that there is no guarantee that the returned element is the only element representing zero in this lattice. Other zeroes may arise from computations, but they will always be equal to the element returned by this method.

      Returns:
      the zero of this lattice.

    • one

      Element one()
      Return the one of this lattice.

      Note that there is no guarantee that the returned element is the only element representing one in this lattice. Other ones may arise from computations, but they will always be equal to the element returned by this method.

      Returns:
      the one of this lattice.

    • comp

      boolean comp​(Element x, Element y)
      Return whether the two provided elements are comparable.
      Parameters:
      x - an element.
      y - another element.
      Returns:
      true if x ≤ y or y ≤ x, false otherwise.

    • leq

      boolean leq​(Element x, Element y)
      Return whether an element is less than or equal to another element in the natural order of this lattice.
      Parameters:
      x - an element.
      y - another element.
      Returns:
      true if x ≤ y, false otherwise.

    • psdiff

      Element psdiff​(Element x, Element y)
      Return the Brouwerian pseudo-difference of two elements (optional operation).

      The (Brouwerian) pseudo-difference of x and y, usually denoted by x − y, is defined by a Galois connection with the join operation (categorically speaking, an adjunction):

      x − y ≤ t  iff  x ≤ y ∨ t  for all t.

      If the Galois connection exists, this lattice is endowed with the structure of a Brouwerian algebra. In that case, if the lattice is finite

      x − y = inf { z | x ≤ y ∨ z },

      and the lattice is necessarily distributive. Conversely, all finite distributive lattices are Brouwerian algebras, with x − y defined as above.

      Parameters:
      x - an element.
      y - another element.
      Returns:
      x − y.
      Throws:
      UnsupportedOperationException - if this lattice is not Browerian.

    • pscomp

      Element pscomp​(Element x, Element y)
      Return the pseudocomplement of the first element relative to the second element (optional operation).

      The pseudocomplement of x relative to y, denoted by x ⇒ y, is defined by a Galois connection with the meet operation (categorically speaking, an adjunction):

      t ≤ y ⇒ x  iff  x ∧ t ≤ y  for all t.

      If the Galois connection exists, this lattice is endowed with the structure of a Heyting algebra. In that case, if the lattice is finite

      x ⇒ y = sup { z | x ∧ z ≤ y },

      and the lattice is necessarily distributive. Conversely, all finite distributive lattices are Heyting algebras.

      Parameters:
      x - an element.
      y - another element.
      Returns:
      x ⇒ y.

    • symdiff

      Element symdiff​(Element x, Element y)
      Return the symmetric difference of the arguments, that is, psdiff(x,y).join(psdiff(y,x)).
      Parameters:
      x - an element.
      y - another element.
      Returns:
      x Δ y.
      See Also:
      Element.join(Element), psdiff(Element, Element)

    • coveringRelation

      Map<Element,​Set<Element>> coveringRelation()
      Return the covering relation of this lattice.

      The covering relation of a lattice relates elements x, y such that there is no element strictly between x and y. In can be interpreted as a graph and drawn, resulting in the Hasse diagram of the lattice.

      Returns:
      a map from elements to set of elements representing the covering relation.