tailieunhanh - Báo cáo khoa học: "Transducers from Rewrite Rules with Backreferences "

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. | Proceedings of EACL 99 Transducers from Rewrite Rules with Backreferences Dale Gerdemann University of Tuebingen KI. Wilhelmstr. 113 D-72074 Tuebingen dg@ Gertjan van Noord Groningen University PO Box 716 NL 9700 AS Groningen vannoord@ 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 backref-erencing leads to more elegant and general solutions. 1 Introduction Context sensitive rewrite rules have been widely used in several areas of natural language processing. Johnson 1972 has shown that such rewrite rules are equivalent to finite state transducers in the special case that they are not allowed to rewrite their own output. An algorithm for compilation into transducers was provided by Kaplan and Kay 1994 . Improvements and extensions to this algorithm have been provided by Karttunen 1995 Karttunen 1997 Karttunen 1996 and Mohri and Sproat 1996 . In this paper the algorithm will be extended to provide a limited form of back-referencing. Backreferencing has been implicit in previous research such as in the batch rules of Kaplan and Kay 1994 bracketing transducers for finite-state parsing Kart-tunen 1996 and the LocalExtension operation of Roche and Schabes 1995 . The explicit use of backreferencing leads to more elegant and general solutions. Backreferencing is widely used in editors scripting languages and other tools employing regular expressions Friedl 1997 . For example Emacs uses the special brackets and to capture strings along with the notation n to recall the nth such string. The expression a b l matches strings of the form anban. Unrestricted use of .