next up previous
Next: Introduction

Transducers from Rewrite Rules with Backreferences

Dale Gerdemann Gertjan van Noord
University of Tuebingen Groningen University
Kl. Wilhelmstr. 113 PO Box 716
D-72074 Tuebingen NL 9700 AS Groningen


Context sensitive rewrite rules have been widely used in several areas of natural language processing, including syntax, morphology, phonology and speech processing. Kaplan and Kay, Karttunen, and Mohri & Sproat have given various algorithms to compile such rewrite rules into finite-state transducers. The present paper extends this work by allowing a limited form of backreferencing in such rules. The explicit use of backreferencing leads to more elegant and general solutions.


Noord G.J.M. van