# Union

## Description

This operation computes the union (sum) 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 union transduces `x` to `y` with weight `a` and `w` to `v` with weight `b`.

## Usage

 ```template void Union(MutableFst *fst1, const Fst &fst2); ``` ```template UnionFst:: UnionFst(const Fst &fst1, const Fst &fst2); ``` %DOX{fst::UnionFst[]}% `fstunion a.fst b.fst out.fst`

## Examples

### `A ∪ B`:

```Union(&A, B);
UnionFst<Arc>(A, B);
fstunion a.fst b.fst out.fst
```

## Complexity

`Union`:

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

`UnionFst:`

• 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 - 1 Jul 2007

Topic attachments
I Attachment History Action Size Date Who Comment
jpg union1.jpg r1 manage 3.4 K 2007-07-01 - 19:04 MichaelRiley
jpg union2.jpg r1 manage 6.3 K 2007-07-01 - 19:05 MichaelRiley
jpg union3.jpg r1 manage 12.6 K 2007-07-01 - 19:06 MichaelRiley
Edit | Watch | Print version | History: r4 < r3 < r2 < r1 | Backlinks | Raw View | More topic actions
Topic revision: r4 - 2018-04-27 - MichaelRiley

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