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
dg@sfs.nphil.uni-tuebingen.de	vannoord@let.rug.nl

Abstract:

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.