edu.cmu.sphinx.fst.semiring

Class Semiring

java.lang.Object

edu.cmu.sphinx.fst.semiring.Semiring

All Implemented Interfaces:

java.io.Serializable

Direct Known Subclasses:

LogSemiring, ProbabilitySemiring, TropicalSemiring

public abstract class Semiring
extends java.lang.Object
implements java.io.Serializable

Abstract semiring class.

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
protected static int	accuracy

Constructor Summary

Constructors

Constructor and Description
Semiring()

Method Summary

Modifier and Type	Method and Description
abstract float	divide(float w1, float w2)
boolean	equals(java.lang.Object obj)
abstract boolean	isMember(float w)
boolean	naturalLess(float w1, float w2) NATURAL ORDER By definition: a <= b iff a + b = a The natural order is a negative partial order iff the semiring is idempotent.
abstract float	one()
abstract float	plus(float w1, float w2)
abstract float	reverse(float w1)
abstract float	times(float w1, float w2)
java.lang.String	toString()
abstract float	zero()

Methods inherited from class java.lang.Object

clone, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

accuracy

protected static final int accuracy

See Also:

Constant Field Values

Constructor Detail

Semiring

public Semiring()

Method Detail

plus

public abstract float plus(float w1,
                           float w2)

reverse

public abstract float reverse(float w1)

times

public abstract float times(float w1,
                            float w2)

divide

public abstract float divide(float w1,
                             float w2)

zero

public abstract float zero()

one

public abstract float one()

isMember

public abstract boolean isMember(float w)

equals

public boolean equals(java.lang.Object obj)

Overrides:

equals in class java.lang.Object

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

naturalLess

public boolean naturalLess(float w1,
                           float w2)

NATURAL ORDER By definition: a <= b iff a + b = a The natural order is a negative partial order iff the semiring is idempotent. It is trivially monotonic for plus. It is left (resp. right) monotonic for times iff the semiring is left (resp. right) distributive. It is a total order iff the semiring has the path property. See Mohri, "Semiring Framework and Algorithms for Shortest-Distance Problems", Journal of Automata, Languages and Combinatorics 7(3):321-350, 2002. We define the strict version of this order below.

Parameters:

w1 - first operand

w2 - second operand

Returns:

less or more