Library Reference

AbstractSemiringNumber{T} <: Number

An element of a unital quantale.

Unital Quantales

A unital quantale is a quadruple $(R, \leq, \times, 1)$, where

• $(R, \leq)$ is a complete lattice
• $(R, \times, 1)$ is a monoid
• multiplication ($\times$) distributes over joins

Each concrete subtype T <: AbstractSemiringNumber defines a unital quantale whose elements are objects of type T. Given such a subtype, we may construct the following elements

• typemin(T): a bottom element
• typemax(T): a top element
• one(T): a multiplicative identity

For all pairs of objects a and b of type T, we may compute the following elements

• star(a): the Kleene star of a
• a + b: the join of a and b
• a & b: the meet of a and b
• b / a: the left residual of b by a
• a \ b: the right residual of b by a

*-Autonomous Quantales

If T is a *-autonomous quantale, then some additional operations are available.

• a': the negation of a
• a ⅋ b the "par" of a and b

MinPlus{T} <: AbstractSemiringNumber{T}

The *-autonomous quantale $([-\infty, +\infty], \geq, +, 0)$.

• elements are extended real numbers: a ∈ $[-\infty, +\infty]$
• the ordering is backwards: $a \geq b$
• multiplication is addition: $a + b$
• the multiplicative identity is $0$

This quantale is sometimes called the tropical semiring.

MaxPlus{T} <: AbstractSemiringNumber{T}

The *-autonomous quantale $([-\infty, +\infty], \leq, +, 0)$.

• elements are extended real numbers: a ∈ $[-\infty, +\infty]$
• the ordering is standard: $a \leq b$
• multiplication is addition: $a + b$
• the multiplicative identity is $0$

This quantale is sometimes called the arctic semiring.

MaxMul{T} <: AbstractSemiringNumber{T}

The *-autonomous quantale $([0, +\infty], \leq, \times, 0)$.

• elements are nonnegative extended real numbers: a ∈ $[0, +\infty]$
• the ordering is standard: $a \leq b$
• multiplication is standard: $a \times b$
• the multiplicative identity is $1$

This quantale is sometimes called the Viterbi semiring.

OrAnd{T} <: AbstractSemiringNumber{T}

The *-autonomous quantale $(2^n, \subseteq, \cap, 2^n)$.

• elements are subsets: $a \in 2^n$
• the ordering is subset inclusion: $a \subseteq b$
• multiplication is intersection: $a \cap b$
• the multiplicative identity is $2^n$

This quantale is sometimes called the powerset semiring.

AndOr{T} <: Number

The *-autonomous quantale $(2^n, \supseteq, \cup, \emptyset)$.

• elements are subsets: $a \in 2^n$
• the ordering is subset exclusion: $a \supseteq b$
• multiplication is union: $a \cup b$
• the multiplicative identity is $\emptyset$

This quantale is sometimes called the powerset semiring.

AbstractStarLU{T} <: AbstractStar{T}

An AbstractStarLU factorization object represents a matrix $A^*$ as a pair $(L, U)$, where

• $L$ is strictly lower triangular
• $U$ is upper triangular

and $A^* = U^* L^*$.

slu(A::AbstractMatrix)

Construct an AbstractStarLU factorization object for the Kleene star $A^*$.