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
:
B
:
A o B
:
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