TWiki> FST Web>FstQuickTour>ComposeDoc (revision 1)EditAttach

Compose

Description

This operation omputes the composition of two transducers. If A transduces string x to y with weight a and B transduces y to z with weight b, then their composition transduces string x to z with weight Times(x, z).

The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight).

Examples

A:

compose1.jpg

B:

compose2.jpg

A o B:

compose3.jpg

Compose(A, B, &C);
ComposeFst<Arc>(A, B);
fstcompose a.fst b.fst out.fst

Complexity

Compose: O((nstates1 + narcs1) * (nstates2 + narcs2))
ComposeFst:

  • Constructor: O(1)
  • Traversal: O((nstates1_visited + narcs1_visited) * (nstates2_visited + narcs2_visited)), assuming constant time to visit an input state or arc.

-- MichaelRiley - 15 Jun 2007

Topic attachments
I Attachment History Action Size Date Who Comment
JPEGjpg compose1.jpg r1 manage 7.7 K 2007-06-16 - 02:55 MichaelRiley  
JPEGjpg compose2.jpg r6 r5 r4 r3 r2 manage 8.6 K 2007-06-16 - 03:22 MichaelRiley  
JPEGjpg compose3.jpg r5 r4 r3 r2 r1 manage 9.9 K 2007-06-16 - 03:22 MichaelRiley  
Edit | Attach | Watch | Print version | History: r24 | r4 < r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r1 - 2007-06-16 - 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