ClosureDoc < FST

---+ 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
=a &otimes; a=, =xxx= to =yyy= with weight =a &otimes; a &otimes; a=,
etc. If =closure_type= is =CLOSURE_STAR=, then the empty string is
transduced to itself with weight =<span style="text-decoration:overline">1</span>= as well.

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

|<verbatim>
template<class Arc>
void Closure(MutableFst<Arc> *fst, ClosureType type);
</verbatim> |  |
|<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=:
   * Time: _O(V)_
   * Space: _O(V)_ %BR%
where _V_ = # of states and _E_ = # of arcs.

=ClosureFst:= 
   * Time: _O(v)_
   * Space: _O(v)_  %BR%
where _v_ = # of states visited, _e_ = # of arcs visited. 
Constant time to visit an input state or arc is assumed and exclusive of [[FstAdvancedUsage#FstCaching][caching]].


-- 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

This topic: FST > WebHome > FstQuickTour > ClosureDoc
Topic revision: r15 - 2018-04-27 - MichaelRiley