# Difference: ReverseDoc (2 vs. 3)

#### Revision 32018-04-27 - MichaelRiley

Line: 1 to 1

 META TOPICPARENT name="FstQuickTour"

# Reverse

## Description

This operation reverses an FST. If `A` transduces string `x` to `y` with weight `a`, then the reverse of `A` transduces the reverse of `x` to the reverse of `y` with weight `a.Reverse()`.

Typically, `a` = `a.Reverse()` and `Arc` = `RevArc` (e.g. for `TropicalWeight` or `LogWeight`). In general, e.g., when the weights only form a left or right semiring, the output arc type must match the input arc type except having the reversed Weight type.

## Usage

|
```template<class Arc, class RevArc>
void Reverse(const Fst<Arc> &ifst, MutableFst<RevArc> *ofst);```
Changed:
<
<
| %DOX{namespacefst.html#Reverse[]}% |
>
>
|
|
`fstreverse a.fst out.fst`
Changed:
<
<
| |
>
>
|

## Examples

### `Reverse of A`:

```Reverse(&A);
fstreverse a.fst out.fst
```

## Complexity

`Reverse`:

• Time: O(V + E)
• Space: O(V + E)
where V = # of states and E = # of arcs.

-- MichaelRiley - 03 Jul 2007

 META FILEATTACHMENT attr="" autoattached="1" comment="" date="1183425553" name="reverse1.jpg" path="reverse1.jpg" size="14649" user="Main.MichaelRiley" version="3" attr="" autoattached="1" comment="" date="1183425575" name="reverse2.jpg" path="reverse2.jpg" size="18957" user="Main.MichaelRiley" version="3"

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