(r10) ClosureDoc < FST

FST Web>FstQuickTour>ClosureDoc (revision 10) (raw view)~~EditAttach~~

---+ Closure

---++ Description
This operation computes the concatenative closure. If =A= transduces string =x= to =y= with weight =a=, then the
closure transduces =x= to =y= with weight =a=, =xx= to =yy= with weight
=Times(a, a)=, =xxx= to =yyy= with weight =Times(Times(a, a), a)=,
etc. If =closure_type= is =CLOSURE_STAR=, then the empty string is
transduced to itself with weight =Weight::One()= as well.

---++ Usage
<verbatim>
enum ClosureType { CLOSURE_STAR, CLOSURE_PLUS };
</verbatim>

|<verbatim>
template<class Arc>
void Closure(MutableFst<Arc> *fst, ClosureType type);
</verbatim> | %DOX{namespacefst.html#Closure[%H%]}% |
|<verbatim>
template <class Arc> ClosureFst<Arc>::
ClosureFst(const Fst<Arc> &fst, ClosureType type);
</verbatim> | %DOX{fst::ClosureFst[%H%]}% |
|<verbatim>
fstclosure [--opts] a.fst out.fst
  --closure_type: closure_star (def) | closure_plus
</verbatim> |  |

---++ Examples

---+++ =A=:

%ATTACHURL%/closure1.jpg

---+++ =A*=:

%ATTACHURL%/closure2.jpg

<verbatim>
Closure(&A, CLOSURE_STAR);
ClosureFst<Arc>(A, CLOSURE_STAR);
fstclosure a.fst out.fst
</verbatim>

---+++ =A+=:

%ATTACHURL%/closure3.jpg

<verbatim>
Closure(&A, CLOSURE_PLUS);
ClosureFst<Arc>(A, CLOSURE_PLUS);
fstclosure --closure_plus a.fst out.fst
</verbatim>

---++ Complexity

=Closure=: _O(V + E)_, where _V_ = # of states and _E_ = # of arcs.

=ClosureFst:= 
   * Constructor: _O(1)_
   * Traversal: _O(v + e)_, %BR% 
      where _v_ = # of states visited, _e_ = # of arcs visited and
      constant time to visit an input state or arc is assumed.


-- Main.MichaelRiley - 13 Jun 2007

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who
jpg	closure1.jpg	r1	manage	3.4 K	2007-06-21 - 21:43	MichaelRiley
jpg	closure2.jpg	r1	manage	6.3 K	2007-06-21 - 21:43	MichaelRiley
jpg	closure3.jpg	r1	manage	4.1 K	2007-06-21 - 21:43	MichaelRiley

Topic revision: r10 - 2007-07-01 - MichaelRiley