Difference: SynchronizeDoc (1 vs. 9)

Revision 92018-04-27 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Synchronize

Line: 17 to 17
 |
template <class Arc>
void Synchronize(const Fst<Arc> &ifst, MutableFst<Arc> *ofst);
Changed:
<
<
| %DOX{namespacefst.html#Synchronize[doc]}% |
>
>
| |
 |
template <class Arc> SynchronizeFst<Arc>::
SynchronizeFst(const Fst<Arc>& fst);

Revision 82009-04-30 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Synchronize

Line: 28 to 28
 

Examples

A:

Changed:
<
<
/twiki/pub/FST/SynchronizeDoc/synchronize1.jpg
>
>
synchronize1.jpg
 

Synchronize of A:

Changed:
<
<
/twiki/pub/FST/SynchronizeDoc/synchronize2.jpg
>
>
synchronize2.jpg
 
Synchronize(A, &B);

Revision 72007-07-04 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Synchronize

Line: 41 to 41
 

Complexity

Synchronize:
Changed:
<
<
  • A has bounded delay: exponential
>
>
  • A has bounded delay: Time and Space complexity is exponential
 
  • A does not have bounded delay: does not terminate
SynchronizeFst:
Changed:
<
<
  • A has bounded delay: exponential
>
>
  • A has bounded delay: Time and Space complexity is exponential
 
  • A does not have bounded delay: does not terminate

References

Revision 62007-07-02 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Synchronize

Line: 41 to 41
 

Complexity

Synchronize:
Changed:
<
<
  • A has bound delay: exponential
  • A does not have bound delay: does not terminate
>
>
  • A has bounded delay: exponential
  • A does not have bounded delay: does not terminate
 SynchronizeFst:
Changed:
<
<
  • Constructor: O(1)
  • Traversal:
    • A has bound delay: exponential
    • A does not have bound delay: does not terminate
>
>
  • A has bounded delay: exponential
  • A does not have bounded delay: does not terminate
 

References

  • Mehryar Mohri.
Line: 57 to 55
 -- CyrilAllauzen - 22 Jun 2007

META FILEATTACHMENT attr="" autoattached="1" comment="Output transducer for synchronize example" date="1182879264" name="synchronize2.jpg" path="synchronize2.jpg" size="12550" user="Main.CyrilAllauzen" version="3"
Changed:
<
<
META FILEATTACHMENT attachment="synchronize1.jpg" attr="" comment="Input transducer for synchronize example" date="1182879625" name="synchronize1.jpg" path="synchronize1.jpg" size="7746" stream="synchronize1.jpg" user="Main.CyrilAllauzen" version="3"
>
>
META FILEATTACHMENT attr="" autoattached="1" comment="Input transducer for synchronize example" date="1182879627" name="synchronize1.jpg" path="synchronize1.jpg" size="7746" user="Main.CyrilAllauzen" version="3"

Revision 52007-06-26 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Synchronize

Line: 56 to 56
  -- CyrilAllauzen - 22 Jun 2007
Changed:
<
<
META FILEATTACHMENT attr="" autoattached="1" comment="Output transducer for synchronize example" date="1182550005" name="synchronize2.jpg" path="synchronize2.jpg" size="27089" user="Main.CyrilAllauzen" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="Input transducer for synchronize example" date="1182549609" name="synchronize1.jpg" path="synchronize1.jpg" size="16792" user="Main.CyrilAllauzen" version="1"
>
>
META FILEATTACHMENT attr="" autoattached="1" comment="Output transducer for synchronize example" date="1182879264" name="synchronize2.jpg" path="synchronize2.jpg" size="12550" user="Main.CyrilAllauzen" version="3"
META FILEATTACHMENT attachment="synchronize1.jpg" attr="" comment="Input transducer for synchronize example" date="1182879625" name="synchronize1.jpg" path="synchronize1.jpg" size="7746" stream="synchronize1.jpg" user="Main.CyrilAllauzen" version="3"

Revision 42007-06-26 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Synchronize

Line: 16 to 17
 |
template <class Arc>
void Synchronize(const Fst<Arc> &ifst, MutableFst<Arc> *ofst); 
Changed:
<
<
| %DOX{namespacefst.html#Synchronize[Help]}% |
>
>
| %DOX{namespacefst.html#Synchronize[doc]}% |
 |
template <class Arc> SynchronizeFst<Arc>::
SynchronizeFst(const Fst<Arc>& fst);
Changed:
<
<
| %DOX{fst::SynchronizeFst[Help]}% |
>
>
| %DOX{fst::SynchronizeFst[doc]}% |
 
 fstsynchronize a.fst out.fst 
 

Revision 32007-06-25 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Synchronize

Line: 51 to 51
 

References

Changed:
<
<
International Journal of Computer Science 14(6): 957-982 (2003).
>
>
International Journal of Computer Science, 14(6): 957-982 (2003).
  -- CyrilAllauzen - 22 Jun 2007

Revision 22007-06-24 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

Synchronize

Line: 13 to 13
 For the algorithm to terminate, the input transducer must have bounded delay, i.e., the delay of every cycle must be zero.

Usage

Changed:
<
<
>
>
|
 template void Synchronize(const Fst &ifst, MutableFst *ofst);
Changed:
<
<
>
>
| %DOX{namespacefst.html#Synchronize[Help]}% | |
 template SynchronizeFst:: SynchronizeFst(const Fst& fst);
Added:
>
>
| %DOX{fst::SynchronizeFst[Help]}% |
 fstsynchronize a.fst out.fst 
 
 
Deleted:
<
<
fstsynchronize a.fst out.fst
 

Examples

Line: 47 to 48
 
    • A has bound delay: exponential
    • A does not have bound delay: does not terminate
Added:
>
>

References

  -- CyrilAllauzen - 22 Jun 2007
Added:
>
>
META FILEATTACHMENT attr="" autoattached="1" comment="Output transducer for synchronize example" date="1182550005" name="synchronize2.jpg" path="synchronize2.jpg" size="27089" user="Main.CyrilAllauzen" version="1"
 
META FILEATTACHMENT attr="" autoattached="1" comment="Input transducer for synchronize example" date="1182549609" name="synchronize1.jpg" path="synchronize1.jpg" size="16792" user="Main.CyrilAllauzen" version="1"
Deleted:
<
<
META FILEATTACHMENT attachment="synchronize2.jpg" attr="" comment="Output transducer for synchronize example" date="1182550003" name="synchronize2.jpg" path="synchronize2.jpg" size="27089" stream="synchronize2.jpg" user="Main.CyrilAllauzen" version="1"

Revision 12007-06-22 - CyrilAllauzen

Line: 1 to 1
Added:
>
>
META TOPICPARENT name="FstQuickTour"

Synchronize

Description

This operation synchronizes a transducer. The result will be an equivalent FST that has the property that during the traversal of a path, the delay is either zero or strictly increasing, where the delay is the difference between the number of non-epsilon output labels and input labels along the path.

For the algorithm to terminate, the input transducer must have bounded delay, i.e., the delay of every cycle must be zero.

Usage

template <class Arc>
void Synchronize(const Fst<Arc> &ifst, MutableFst<Arc> *ofst);

template <class Arc> SynchronizeFst<Arc>::
SynchronizeFst(const Fst<Arc>& fst);

fstsynchronize a.fst out.fst

Examples

A:

/twiki/pub/FST/SynchronizeDoc/synchronize1.jpg

Synchronize of A:

/twiki/pub/FST/SynchronizeDoc/synchronize2.jpg

Synchronize(A, &B);
SynchronizeFst<Arc>(A);
fstsynchronize a.fst out.fst

Complexity

Synchronize:
  • A has bound delay: exponential
  • A does not have bound delay: does not terminate
SynchronizeFst:
  • Constructor: O(1)
  • Traversal:
    • A has bound delay: exponential
    • A does not have bound delay: does not terminate

-- CyrilAllauzen - 22 Jun 2007

META FILEATTACHMENT attr="" autoattached="1" comment="Input transducer for synchronize example" date="1182549609" name="synchronize1.jpg" path="synchronize1.jpg" size="16792" user="Main.CyrilAllauzen" version="1"
META FILEATTACHMENT attachment="synchronize2.jpg" attr="" comment="Output transducer for synchronize example" date="1182550003" name="synchronize2.jpg" path="synchronize2.jpg" size="27089" stream="synchronize2.jpg" user="Main.CyrilAllauzen" version="1"
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback