TWiki> FST Web>FstQuickTour>ClosureDoc (revision 9)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 void Closure(MutableFst *fst, ClosureType type); ``` [bad link?] ```template ClosureFst:: ClosureFst(const Fst &fst, ClosureType type); ``` ```fstclosure [--opts] a.fst out.fst --closure_type: closure_star (def) | closure_plus ```

Examples

`A*`:

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

`A+`:

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

Complexity

`Closure`: O(V + E), where V = # of states and E = # of arcs.

`ClosureFst:`

• Constructor: O(1)
• Traversal: O(v + e),
where v = # of states visited and e = # of arcs visited and assuming constant time to visit an input state or arc.

-- MichaelRiley - 13 Jun 2007

Topic attachments
I Attachment History Action Size Date Who Comment
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
Edit | Attach | Watch | Print version |  | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r9 - 2007-06-30 - MichaelRiley

Copyright © 2008-2023 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback