Paper: An Efficient Compiler For Weighted Rewrite Rules

ACL ID P96-1031
Title An Efficient Compiler For Weighted Rewrite Rules
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1996
Authors

Context-dependent rewrite rules are used in many areas of natural language and speech processing. Work in computa- tional phonology has demonstrated that, given certain conditions, such rewrite rules can be represented as finite-state transducers (FSTs). We describe a new algorithm for compiling rewrite rules into FSTs. We show the algorithm to be sim- pler and more efficient than existing al- gorithms. Further, many of our appli- cations demand the ability to compile weighted rules into weighted FSTs, trans- ducers generalized by providing transi- tions with weights. We have extended the algorithm to allow for this. 1. Motivation Rewrite rules are used in many areas of natural language and speech processing, including syntax, morphology, and phonology 1. In interesting ap- plications, the...