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'):

• zero(Val).

• plus(Val0,Val1,Sum).

• minus(Val0,Val1,Diff).

• minimum(Val0,Val1,MinVal).

• minimum_only(YesNo).

Currently, the following types of transducers are supported:

• fsa_strings (ordinary (string-to-string) transducers)

• fsa_weights (weighted recognizers, aka string-to-weight transducers)

• fsa_weighted_strings (weighted transducers, aka string-to-weighted-string transducer).

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

• yes

• no

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'.