Compiling a Partition-Based Two-Level Formalism

Compiling a Partition-Based Two-Level Formalism Edmund Grimley-Evans* University of Cambridge (St John's College) Computer Laboratory Cambridge CB2 3QG, UK Edmund. Grimley-Evans@cl. cam. ac. uk George Anton Kiraz t University of Cambridge (St John's College) Computer Laboratory Cambridge CB2 3QG, UK George. Kiraz@cl. cam. ac. uk Stephen G. Pulman University of Cambridge Cointmter Laboratory Cambridge CB2 3QG, UK and SRI International, Cambridge sgpOcam, sri. com Abstract This paper describes an algorithm for the compilation of a two (or more) level or- thographic or phonological rule notation into finite state transducers. The no- tation is an alternative to the standard one deriving from Koskenniemi's work: it is believed to have some practical de- scriptive advantages, and is quite widely used, but has a different interpretation. Etficient interpreters exist for the nota- tion, but until now it has not been clear how to compile to equivalent automata in a transparent way. The present paper shows how to do this, using some of the conceptual tools provided by Kaplan and Kay's regular relations calculus. 1 Introduction Two-level formalisins based on that introduced by (Koskenniemi, 1983) (see also (Ritchie et al., 1992) and (Kaplan and Kay, 1994)) are widely used in practical NLP systems, and are deservedly regarded as something of a standard. However, there is at least one serious rival two-level notation in existence, developed in response to practical difficulties encountered in writing large-scale mor- phological descriptions using Koskenniemi's nota- tion. Tile formalism was first introduced in (Black et al., 1987), was adapted by (Ruessink, 1989), and an extended version of it was proposed for use in the European Commission's ALEP language engineering platform (Pulman, 1991). A flmther extension to the formalisln was described in (Pul- man and Hepple, 1993). The alternative partition tbrmalism was mo- tivated by several perceived practical disadvan- *Supported by SERC studentship no. 92313384. tSupported by a Benefactors' Studentship from St John's College. rages to Koskenniemi's notation. These are de- tailed more fully in (Black et al., 1987, pp. 13-15), and in (Ritchie et al., 1992, pp. 181-9). In brief: (1) Koskennienli rules are not easily interpretable (by tile grammarian) locally, for the interpretation of 'feasible pairs' depends on other rules in the set. (2) There are frequently interactions between rules: whenever the lexieal/surface pair affected by a rule A appears in tile context of another rule B, the grammarian must check that its appearance in rule B will not conflict with the requirements of rule A. (3) Contexts may conflict: the same lexical character may obligatorily have multiple realisa- tions in different contexts, but it may be impossi- ble to state the contexts in ways that do not block a desired application. (4) Restriction to single character changes: whenever a change affecting more than one adjacent character occurs, multi- ple rules nmst be written. At best this prompts tile interaction problem, and at worst can require the rules to be forInulated with under-restrictive contexts to avoid mutual blocking. (5) There is no mechanism for relating particular rules to spe- …

Content truncated to 500 words