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);
 
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  
Edit | Attach | Watch | Print version | History: r15 < r14 < r13 < r12 < r11 | Backlinks | Raw View | WYSIWYG | More topic actions
Topic revision: r15 - 2018-04-27 - 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