TWiki> FST Web>FstQuickTour>ClosureDoc (revision 8)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

enum ClosureType { CLOSURE_STAR, CLOSURE_PLUS };

template<class Arc>
void Closure(MutableFst<Arc> *fst, ClosureType type);
doc [bad link?]
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: O(nstates + narcs)
ClosureFst:

  • Constructor: O(1)
  • Traversal: O(nstates_visited + narcs_visited),
    assuming constant time to visit an input state or arc.

-- MichaelRiley - 13 Jun 2007

Topic attachments
I Attachment History Action Size Date Who CommentSorted ascending
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  
Edit | Attach | Watch | Print version | History: r15 | r10 < r9 < r8 < r7 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r8 - 2007-06-30 - MichaelRiley
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback