Line: 1 to 1  

Compose  
Line: 20 to 20  
template <class Arc> void Compose(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2, MutableFst<Arc> *ofst);  
Changed:  
< <   [bad link?]   
> >     
template <class Arc> ComposeFst<Arc>:: ComposeFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2); 
Line: 1 to 1  

Compose  
Line: 86 to 86  
See here for more discussion on efficient usage.  
Changed:  
< <   MichaelRiley  15 Jun 2007  
> >  See Also  

Line: 1 to 1  

Compose  
Line: 84 to 84  
or the input side of the second transducer or prefer placing them later in a path since they delay matching and can introduce noncoaccessible states and transitions  
Added:  
> >  See here for more discussion on efficient usage.  
 MichaelRiley  15 Jun 2007

Line: 1 to 1  

Compose  
Line: 74 to 74  
Compose and fstcompose trim their output, ComposeFst does not (since it is a delayed operation).
The efficiency of composition can be strongly affected by several factors:  
Changed:  
< < 
 
> > 
 
 
Changed:  
< <  delay matching and can introduce noncoaccessible states and transitions.  
> >  delay matching and can introduce noncoaccessible states and transitions  
 MichaelRiley  15 Jun 2007 
Line: 1 to 1  

Compose 
Line: 1 to 1  

Compose  
Line: 12 to 12  
matchers).
The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight for instance).  
Changed:  
< <  Versions of this operation (not all shown here) accept options that allow choosing the matcher, composition filter, state table and, when delayed, the caching behaviour used by composition.  
> >  Versions of this operation (not all shown here) accept options that allow choosing the matcher, composition filter, state table and, when delayed, the caching behavior used by composition.  
Usage 
Line: 1 to 1  

Compose  
Line: 10 to 10  
The output labels of the first transducer or the input labels of the second transducer must be sorted (or the FSTs otherwise support appropriate matchers).  
Changed:  
< <  The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight ).  
> >  The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight for instance).
Versions of this operation (not all shown here) accept options that allow choosing the matcher, composition filter, state table and, when delayed, the caching behaviour used by composition.  
Usage  
Line: 63 to 66  
 
Changed:  
< <  Constant time and space to visit an input state or arc is assumed and exclusive of caching.  
> >  Constant time and space to visit an input state or arc is assumed and exclusive of caching.  
Caveats 
Line: 1 to 1  

Compose  
Line: 10 to 10  
The output labels of the first transducer or the input labels of the second transducer must be sorted (or the FSTs otherwise support appropriate matchers).  
Changed:  
< <  The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight ).  
> >  The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight ).  
Usage 
Line: 1 to 1  

Compose  
Line: 8 to 8  
transduces y to z with weight b , then their composition transduces
string x to z with weight a ⊗ b .  
Changed:  
< <  The output labels of the first transducer or the input labels of the second transducer must be sorted.  
> >  The output labels of the first transducer or the input labels of the second transducer must be sorted (or the FSTs otherwise support appropriate matchers).  
The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight ).
Usage 
Line: 1 to 1  

Compose  
Line: 6 to 6  
This operation computes 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  
Changed:  
< <  string x to z with weight Times(x, z) .  
> >  string x to z with weight a ⊗ b .  
The output labels of the first transducer or the input labels of the second transducer must be sorted.
The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight ). 
Line: 1 to 1  

Compose  
Line: 70 to 70  
Compose and fstcompose trim their output, ComposeFst does not (since it is a delayed operation).
The efficiency of composition can be strongly affected by several factors:  
Changed:  
< < 
 
> > 
 

Line: 1 to 1  

Compose  
Line: 52 to 52  
Assuming the first FST is unsorted and the second is sorted:
 
Changed:  
< < 
 
> > 
 
ComposeFst :  
Changed:  
< < 
 
> > 
 
 
Changed:  
< <  where v_{i} = # of states visited and d_{i} = maximum outdegree of the states visited.for the ith FST.  
> >  where v_{i} = # of states visited, d_{i} = maximum outdegree, and m_{i} = maximum multiplicity of the states visited.for the ith FST.  
Constant time and space to visit an input state or arc is assumed and exclusive of caching.  
Line: 72 to 72  
The efficiency of composition can be strongly affected by several factors:
 
Added:  
> > 
 

Line: 1 to 1  

Compose  
Line: 51 to 51  
Assuming the first FST is unsorted and the second is sorted:  
Changed:  
< <  Compose : O(V_{1} V_{2} D_{1} log D_{2}),  
> >  Compose :
 
where V_{i} = # of states and D_{i} = maximum outdegree
for the ith FST.
 
Changed:  
< < 
 
> > 
 
where v_{i} = # of states visited and d_{i} = maximum outdegree of the  
Changed:  
< <  states visited.for the ith FST and constant time to visit an input state or arc is assumed.  
> >  states visited.for the ith FST. Constant time and space to visit an input state or arc is assumed and exclusive of caching.  
Caveats 
Line: 1 to 1  

Compose  
Line: 13 to 13  
Usage  
Changed:  
< <    
> >  template <class Arc>  
void Compose(const Fst  
Line: 58 to 59  
 
Changed:  
< <  states visited.for the ith FST and assuming constant time to visit an input state or arc.  
> >  states visited.for the ith FST and constant time to visit an input state or arc is assumed.  
Caveats 
Line: 1 to 1  

Compose  
Line: 13 to 13  
Usage  
Changed:  
< <  template <class Arc>  
> >    
void Compose(const Fst  
Line: 51 to 50  
Assuming the first FST is unsorted and the second is sorted:  
Changed:  
< <  Compose : O((nstates1 * nstates2 * max_out_degree1 log(max_out_degree2)) ComposeFst:  
> >  Compose : O(V_{1} V_{2} D_{1} log D_{2}),
where V_{i} = # of states and D_{i} = maximum outdegree
for the ith FST.
 
 
Changed:  
< < 
 
> > 
 
Caveats  
Line: 71 to 74  
 MichaelRiley  15 Jun 2007  
Changed:  
< < 
 
> > 

Line: 1 to 1  

Compose  
Line: 46 to 46  
fstcompose a.fst b.fst out.fst  
Added:  
> >  
ComplexityAssuming the first FST is unsorted and the second is sorted:  
Line: 56 to 57  
 
Added:  
> >  
Caveats
 
Line: 63 to 65  
The efficiency of composition can be strongly affected by several factors:
 
Changed:  
< < 
 
> > 
 
or the input side of the second transducer or prefer placing them later in a path since they delay matching and can introduce noncoaccessible states and transitions. 
Line: 1 to 1  

Compose  
Line: 22 to 22  
ComposeFst(const Fst  
Changed:  
< <  fstcompose a.fst b.fst out.fst connect: Trim output (def: true)  
> >  fstcompose [opts] a.fst b.fst out.fst connect: Trim output (def: true)  
 
Examples 
Line: 1 to 1  

Compose  
Line: 13 to 13  
Usage  
Changed:  
< <  
> >    
template  
Changed:  
< <  
> >   [bad link?]    
template  
Changed:  
< <  
> >      
fstcompose a.fst b.fst out.fst connect: Trim output (def: true)  
Changed:  
< <  
> >     
Examples 
Line: 1 to 1  

Compose  
Line: 21 to 21  
ComposeFst(const Fst fstcompose a.fst b.fst out.fst  
Added:  
> >  connect: Trim output (def: true)  
Examples  
Line: 66 to 67  
 MichaelRiley  15 Jun 2007  
Changed:  
< < 
 
> > 

Line: 1 to 1  

Compose 
Line: 1 to 1  

Compose  
Line: 46 to 46  
Complexity  
Changed:  
< <  Compose : O((nstates1 + narcs1) * (nstates2 + narcs2))  
> >  Assuming the first FST is unsorted and the second is sorted:
 
ComposeFst:
 
Changed:  
< < 
 
> > 
 
Caveats 
Line: 1 to 1  

Compose
Description  
Changed:  
< <  This operation omputes the composition of two transducers. If A transduces string x to y with weight a and B  
> >  This operation computes 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) .  
Line: 51 to 51  
 
Added:  
> >  Caveats
The efficiency of composition can be strongly affected by several factors:
 
 MichaelRiley  15 Jun 2007

Line: 1 to 1  

Compose  
Line: 8 to 8  
transduces y to z with weight b , then their composition transduces
string x to z with weight Times(x, z) .  
Changed:  
< <  The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight ).  
> >  The output labels of the first transducer or the input labels of the second transducer must be sorted.
The weights need to form a commutative semiring (valid for
Usage
template <class Arc> void Compose(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2, MutableFst<Arc> *ofst); template <class Arc> ComposeFst<Arc>:: ComposeFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2); fstcompose a.fst b.fst out.fst  
Examples 
Line: 1 to 1  

Added:  
> > 
Compose
Description
This operation omputes the composition of two transducers. If
The weights need to form a commutative semiring (valid for
Examples

META FILEATTACHMENT  attr="" autoattached="1" comment="" date="1181964136" name="compose2.jpg" path="compose2.jpg" size="8826" user="Main.MichaelRiley" version="6" 

META FILEATTACHMENT  attr="" autoattached="1" comment="" date="1181962547" name="compose1.jpg" path="compose1.jpg" size="7902" user="Main.MichaelRiley" version="1" 
META FILEATTACHMENT  attr="" autoattached="1" comment="" date="1181964162" name="compose3.jpg" path="compose3.jpg" size="10184" user="Main.MichaelRiley" version="5" 