Importance

Loading Importance Indicators...

Abstract

A system and method for compiling weighted context-dependent rewrite rules into weighted finite-state transducers introduces context marking symbols only when and where they are needed. In particular, the compiler and compiling method use a composition of five simple finite-state transducers generated from a weighted context-dependent rewrite rule to represent that rule. An 'r' finite-state transducer is generated from the right context portion .rho. of the weighted context-dependent rewrite rule. An 'f' finite-state transducer is generated from the rewritten portion .phi. of the weighted context-dependent rewrite rule. A 'Replace' finite-state transducer is generated from the rewritten and replacement portions .phi. and .psi. of the weighted context-dependent rewrite rule. Finally, 'l.sub.1 ' and 'l.sub.2 ' finite-state transducers are generated from the left context portion .lambda. of the weighted context-dependent rewrite rule. The 'r' and 'f' finite-state transducer generators of the compiler and the transducer generating steps of the compiling method introduce the context marking symbols '<.sub.1 ', '<.sub.2 ' and '>' in the various finite-state transducers only when and where they are needed. The right context marker symbol '>' is added to the 'r' finite-state transducer only immediately before each occurrence of .rho.. The left context markers '<.sub.1 ' and '<.sub.2 ' are added to the 'f' finite-state transducer only immediately before each occurrence of .phi., neglecting any occurrences of the right marker symbol '>'. The 'Replace', 'l.sub.1 ' and 'l.sub.2 ' finite-state transducers then appropriately remove the right and left context markers when replacing .phi. with .psi., and whether .lambda. precedes .phi. in the input string.

Loading the Abstract Image...

First Claim