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 ⊗ a, xxx to yyy with weight a ⊗ a ⊗ a, etc. If closure_type is CLOSURE_STAR, then the empty string is transduced to itself with weight 1 as well.

Usage

enum ClosureType { CLOSURE_STAR, CLOSURE_PLUS };

template<class Arc>
void Closure(MutableFst<Arc> *fst, ClosureType type);
doc
template <class Arc> ClosureFst<Arc>::
ClosureFst(const Fst<Arc> &fst, ClosureType type);
doc
fstclosure [--opts] a.fst out.fst
  --closure_type: closure_star (def) | closure_plus
 

Examples

A:

closure1.jpg

A*:

closure2.jpg

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

A+:

closure3.jpg

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

Complexity

Closure:

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

ClosureFst:

  • Time: O(v)
  • Space: O(v)
where v = # of states visited, e = # of arcs visited. Constant time to visit an input state or arc is assumed and exclusive of caching.

-- MichaelRiley - 13 Jun 2007

Topic attachments
I Attachment History Action Size Date Who Comment
JPEGjpg closure1.jpg r1 manage 3.4 K 2007-06-21 - 21:43 MichaelRiley  
JPEGjpg closure2.jpg r1 manage 6.3 K 2007-06-21 - 21:43 MichaelRiley  
JPEGjpg closure3.jpg r1 manage 4.1 K 2007-06-21 - 21:43 MichaelRiley  
Topic revision: r14 - 2009-03-06 - CyrilAllauzen
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2014 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback

escort ankara escort beylikduzu escort istanbul escort eskisehir escort bursa mersin escort adana escort izmir escort gaziantep escort antalya escort