TWiki> FST Web>FstQuickTour>ComposeDoc (revision 23)EditAttach

# Compose

## Description

This operation computes the composition of two transducers. If `A` transduces string `x` to `y` with weight `a` and `B` transduces `y` to `z` with weight `b`, then their composition transduces string `x` to `z` with weight `a ⊗ b`.

The output labels of the first transducer or the input labels of the second transducer must be sorted (or the FSTs otherwise support appropriate matchers). The weights need to form a commutative semiring (valid for `TropicalWeight` and `LogWeight` for instance).

Versions of this operation (not all shown here) accept options that allow choosing the matcher, composition filter, state table and, when delayed, the caching behavior used by composition.

## Usage

 ```template void Compose(const Fst &ifst1, const Fst &ifst2, MutableFst *ofst); ``` [bad link?] ```template ComposeFst:: ComposeFst(const Fst &fst1, const Fst &fst2); ``` ```fstcompose [--opts] a.fst b.fst out.fst --connect: Trim output (def: true) ```

## Examples

### `A o B`:

```Compose(A, B, &C);
ComposeFst<Arc>(A, B);
fstcompose a.fst b.fst out.fst
```

## Complexity

Assuming the first FST is unsorted and the second is sorted:

`Compose`:

• Time: O(V1 V2 D1 (log D2 + M2))
• Space: O(V1 V2 D1 M2)
where Vi = # of states, Di = maximum out-degree and Mi = maximum multiplicity for the ith FST.

`ComposeFst`:

• TIme: O(v1 v2 d1 (log d2 + m2)),
• Space: O(v1 v2)
where vi = # of states visited, di = maximum out-degree, and mi = maximum multiplicity of the states visited.for the ith FST. Constant time and space to visit an input state or arc is assumed and exclusive of caching.

## Caveats

`Compose` and `fstcompose` trim their output, `ComposeFst` does not (since it is a delayed operation).

The efficiency of composition can be strongly affected by several factors:

• the choice of which transducer is sorted
• prefer sorting the FST that has the greater average out-degree
• sorting both transducers allows composition to automatically select the best transducer to match against (per state pair)
• note stored sort properties of the FSTs are first checked in constant time followed by the minimum number of linear-time sort tests necessary to discover one sorted FST; thus composition may be unaware that both FSTs are sorted when those properties are not stored.
• the amount of non-determinism
• the presence and location of epsilon transitions - avoid epsilon transitions on the output side of the first transducer or the input side of the second transducer or prefer placing them later in a path since they delay matching and can introduce non-coaccessible states and transitions

See here for more discussion on efficient usage.