Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a novel compilation scheme for finite-state transducers (FSTs) that utilizes the "worsening trick" to efficiently generate and filter rewrite rules of the form $A \to B / L \, \_ \, R$. This approach addresses the complexities of overlapping matches and context constraints in traditional methods, resulting in shorter, uniform formulas that maintain compatibility with existing transducer outputs. The implementation in PyFoma not only simplifies the construction process but also validates its effectiveness against established benchmarks, achieving exact matches in transducer outputs, barring state numbering differences.
Compiling rewrite rules with the "worsening trick" yields a more efficient and extensible framework for finite-state transducers that matches traditional outputs while simplifying the construction process.
Finite-state transducers (FSTs) are essential for modeling string rewriting in computational linguistics and natural language processing (NLP), particularly for phonological and morphological rewrite rules. Compiling general rewrite rules of the form $A \to B / L \, \_ \, R$, where $A$, $B$, $L$, and $R$ are arbitrary regular languages, is complex due to overlapping matches and context constraints. Traditional methods, such as those by Kaplan and Kay or Karttunen, rely on intricate transducer compositions with auxiliary markers. This paper presents a compact compilation scheme based on the "worsening trick'': generate all legal rewrite candidates, then filter candidates that are worse than another candidate for the same input. Implemented as the built-in rewrite compiler in PyFoma, the construction supports multiple contexts, arbitrary transductions, markup, directed rewriting, weights, and parallel rewriting. The resulting formulas are short and uniform, and where semantics coincide, they reproduce the same rule transducers as earlier approaches while remaining easier to extend. The implementation has been validated against foma on both a substantial collection of rewrite grammars and an automated regression suite covering the major rewrite modalities, with the resulting transducers matching exactly apart from state numbering.