2506.17942

#1 Tutorial: $\varphi$-Transductions in OpenFst via the Gallic Semiring [PDF] [Copy] [Kimi] [REL]

Authors: Marco Cognetta, Cyril Allauzen

OpenFst, a popular finite-state transducer library, supports $\varphi$-transitions but, due to an implementation constraint, they cannot be used with transducers in a straightforward way. In this short tutorial, we describe how one can use other functionality provided by OpenFst (namely, the Gallic semiring) to correctly implement $\varphi$-transductions and demonstrate it by implementing the MaxMatch (WordPiece) tokenization algorithm (Devlin et al., 2019; Song et al., 2021). Accompanying self-contained code examples are provided. https://www.openfst.org/twiki/pub/Contrib/FstContrib/phi_transduction_tutorial_code.tgz

Subjects: Formal Languages and Automata Theory , Computation and Language

Publish: 2025-06-22 08:24:04 UTC

---