Closure

Description

This operation computes the concatenative closure. If A transduces 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.

Examples

A:

A*:

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

A+:

Closure(&A, CLOSURE_PLUS);
ClosureFst(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