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

• 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
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: r12 - 2007-07-02 - MichaelRiley

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