InvertDoc < FST

---+ Invert

---++ Description
This operation inverts the transduction corresponding to an FST by
exchanging the FST's input and output labels.

---++ Usage

|<verbatim>
template<class Arc>
void Invert(MutableFst<Arc> *fst);
</verbatim> | |
|<verbatim>
template <class Arc> InvertFst<Arc>::
InvertFst(const Fst<Arc> &fst);
</verbatim> | %DOX{fst::InvertFst[%H%]}% |
|<verbatim>
fstinvert a.fst out.fst
</verbatim> |  |

---++ Examples

---+++ =A=:

%ATTACHURL%/invert1.jpg

---+++ =A<sup>-1</sup>=:

%ATTACHURL%/invert2.jpg

<verbatim>
Invert(&A);
InvertFst<Arc>(A);
fstinvert a.fst out.fst
</verbatim>

---++ Complexity

=Invert=: 
   * Time: _O(V + E)_
   * Space: _O(1)_ %BR%
where _V_ = # of states and _E_ = # of arcs.

=InvertFst:= 
   * Time:: _O(v + e)_
   * Space: _O(1)_ %BR% 
where _v_ = # of states visited, _e_ = # of arcs visited.
Constant time and space to visit an input state or arc is assumed and exclusive of caching.


-- Main.MichaelRiley - 1 Jul 2007

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
jpg	invert1.jpg	r1	manage	5.5 K	2007-07-02 - 03:03	MichaelRiley
jpg	invert2.jpg	r1	manage	5.5 K	2007-07-02 - 03:03	MichaelRiley

This topic: FST > WebHome > FstQuickTour > InvertDoc
Topic revision: r3 - 2018-04-27 - MichaelRiley