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 and 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 and 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 Detail

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 Detail

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.