TWiki> FST Web>FstQuickTour>ConcatDoc (revision 13)EditAttach

# 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); ``` [bad link?] ```template void Concat(const Fst &fst1, MutableFst *fst2); ``` [bad link?] ```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.

-- MichaelRiley - 15 Jun 2007

Topic attachments
I Attachment History Action Size Date Who Comment
jpg concat2.jpg r1 manage 3.4 K 2007-06-21 - 21:43 MichaelRiley
jpg concat1.jpg r1 manage 6.3 K 2007-06-21 - 21:43 MichaelRiley
jpg concat3.jpg r1 manage 10.6 K 2007-06-21 - 21:43 MichaelRiley
Edit | Attach | Watch | Print version |  | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r13 - 2009-03-02 - CyrilAllauzen

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