The Replace Operator

The Replace Operator Lauri Karttunen Rank Xerox Research Centre 6, chemin de Maupertuis F-38240 Meylan, France lauri, karttunen@xerox, fr Abstract This paper introduces to the calculus of regular expressions a replace operator and defines a set of replacement expressions that concisely encode alternate variations of the operation. Replace expressions de- note regular relations, defined in terms of other regular expression operators. The basic case is unconditional obligatory re- placement. We develop several versions of conditional replacement that allow the op- eration to be constrained by context O. Introduction Linguistic descriptions in phonology, morphology, and syntax typically make use of an operation that replaces some symbol or sequence of symbols by another sequence or symbol. We consider here the replacement operation in the context of finite-state grammars. Our purpose in this paper is twofold. One is to define replacement in a very general way, explicitly allowing replacement to be constrained by input and output contexts, as in two-level rules (Koskenniemi 1983), but without the restriction of only single-symbol replacements. The second ob- jective is to define replacement within a general calculus of regular expressions so that replace- ments can be conveniently combined with other kinds of operations, such as composition and un- ion, to form complex expressions. Our replacement operators are close relatives of the rewrite-operator defined in Kaplan and Kay 1994, but they are not identical to it. We discuss their relationship in a section at the end of the paper. 0. 1. Simple regular expressions The replacement operators are defined by means of regular expressions. Some of the operators we use to define them are specific to Xerox implementa- tions of the finite-state calculus, but equivalent formulations could easily be found in other nota- tions. The table below describes the types of expressions and special symbols that are used to define the replacement operators. [1] (A) option (union of A with the empty string) ~A complement (negation) \A term complement (any symbol other than A) $A contains (all strings containing at least one A) A* Kleene star A+ Kleene plus A/B ignore (A interspersed with strings from B) A B concatenation A [ B union A & B intersection A - B relative complement (minus) A . x. B crossproduct (Cartesian product) A . o. B composition Square brackets, [ l, are used for grouping expres- sions. Thus [AI is equivalent to A while (A) is not. The order in the above table corresponds to the precedence of the operations. The prefix operators (-, \, and $) bind more tightly than the postfix operators (*, +, and/), which in turn rank above concatenation. Union, intersection, and relative complement are considered weaker than concate- nation but stronger than crossproduct and compo- sition. Operators sharing the same precedence are interpreted left-to-right. Our new replacement operator goes in a class between the Boolean op- erators and composition. Taking advantage of all these conventions, the fully bracketed expression [2] [[[~[all* [[b]/x]] I el .x. d ; 16 can be rewritten more concisely as …

Content truncated to 500 words