# Concat

## Description

This operation computes the concatenation (product) of two FSTs. If `A` transduces string `x` to `y` with weight `a` and `B` transduces string `w` to `v` with weight `b`, then their concatenation transduces string `xw` to `yv` with weight `a ⊗ b`.

## Usage

 ```template void Concat(MutableFst *fst1, const Fst &fst2); ``` ```template void Concat(const Fst &fst1, MutableFst *fst2); ``` ```template ConcatFst:: ConcatFst(const Fst &fst1, const Fst &fst2); ``` `fstconcat a.fst b.fst out.fst`

## Examples

### `AB`:

```Concat(&A, B);
Concat(A, &B);
ConcatFst<Arc>(A, B);
fstconcat a.fst b.fst out.fst
```

## Complexity

`Concat(&A, B)`:

• Time: O(V1 + V2 + E2)
• Space: O(V1 + V2 + E2)
where Vi = # of states and Ei = # of arcs of the ith FST.

`Concat(A, &B)`:

• Time: O(V1 + E1)
• Space: O(V1 + E1)
where Vi = # of states and Ei = # of arcs of the ith FST.

`ConcatFst:`

• Time: O(v1 + e1 + v2 + e2)
• Space: O(v1 + v2)
where vi = # of states visited and ei = # of arcs visited of the ith FST. Constant time and space to visit an input state or arc is assumed and exclusive of caching.

## Caveats

When concatenating a large number of FSTs, one should use the prepending `Concat(A, &B)` instead of the appending `Concat(&A, B)` since the total cost of the concatenation operations would be linear in the sum of the size of the input FSTs for the former instead of quadratic for the latter.

-- MichaelRiley - 15 Jun 2007

Topic attachments
I Attachment History Action Size Date Who Comment
jpg concat1.jpg r1 manage 6.3 K 2007-06-21 - 21:43 MichaelRiley
jpg concat2.jpg r1 manage 3.4 K 2007-06-21 - 21:43 MichaelRiley
jpg concat3.jpg r1 manage 10.6 K 2007-06-21 - 21:43 MichaelRiley

This topic: FST > WebHome > FstQuickTour > ConcatDoc
Topic revision: r17 - 2018-04-27 - MichaelRiley

Copyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback