TWiki> FST Web>FstQuickTour>UnionDoc (revision 1)EditAttach

# 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); ``` [bad link?] ```template UnionFst:: UnionFst(const Fst &fst1, const Fst &fst2); ``` `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`: O(V2 + E2), where Vi = # of states and Ei = # of arcs of the ith FST.

`UnionFst:`

• Constructor: O(1)
• Traversal: O(v1 + e1 + v2 + e2),
where vi = # of states visited and ei = # of arcs visited of the ith FST and constant time to visit an input state or arc is assumed.

-- 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 | Attach | Watch | Print version |  | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r1 - 2007-07-01 - 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