(r4) SynchronizeDoc < FST

FST Web>FstQuickTour>SynchronizeDoc (revision 4) (raw view)~~EditAttach~~

---+ Synchronize

---++ Description

This operation synchronizes a transducer. The result will be an [[FstGlossary#EquivalentDef][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

|<verbatim>
template <class Arc>
void Synchronize(const Fst<Arc> &ifst, MutableFst<Arc> *ofst);
</verbatim>| %DOX{namespacefst.html#Synchronize[%H%]}% |
|<verbatim>
template <class Arc> SynchronizeFst<Arc>::
SynchronizeFst(const Fst<Arc>& fst);
</verbatim>| %DOX{fst::SynchronizeFst[%H%]}% |
|<verbatim>fstsynchronize a.fst out.fst</verbatim>| |


---++ Examples

---+++ =A=:
%ATTACHURLPATH%/synchronize1.jpg

---+++ =Synchronize of A=:
%ATTACHURLPATH%/synchronize2.jpg

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

---++ 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_

---++ References
   * Mehryar Mohri.
      [[http://www.cs.nyu.edu/~mohri/postscript/edit.pdf][Edit-Distance of Weighted Automata: General Definitions and Algorithms]], 
      _International Journal of Computer Science_, 14(6): 957-982 (2003).

-- Main.CyrilAllauzen - 22 Jun 2007

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
jpg	synchronize1.jpg	r1	manage	16.4 K	2007-06-22 - 22:00	CyrilAllauzen	Input transducer for synchronize example
jpg	synchronize2.jpg	r1	manage	26.5 K	2007-06-22 - 22:06	CyrilAllauzen	Output transducer for synchronize example

Topic revision: r4 - 2007-06-26 - MichaelRiley