contents index next

6. Types of transducers

The determinization, minimization and minimum path algorithms for transducers are implemented in a fully general way, i.e., for various types of transducers (`semirings').

For each supported type, a number of predicates must be defined in a corresponding module (these are called `semiring declarations'):

Currently, the following types of transducers are supported:

The examples directory SemiringModules might contain additional semiring declarations.

6.1. zero(?Val).

The identity element for addition. For strings, this is the empty string; for weights it is 0.

6.2. plus(+Val0,+Val1,?Sum).

Addition. For weights this is number addition, for strings this is concatenation.

6.3. minus(+Val0,+Val1,?Diff).

Inverse of the addition operator.

6.4. minimum(+Val0,+Val1,?Min).

Minimum value of two given values. For weights this is the minumum of two numbers, for strings this is the longest common prefix.

6.5. minimum_only(+YesNo).

YesNo is one of the atoms

indicating whether we are intested in all outputs associated with a path or only in the minimal output. For weights this is `yes', for strings this is `no'.

contents index next