Computer Science
ComputerScience,1970-2008-Computer Science-1994.jsonl.gz.gz
Computer Science
4cca132fcae223e84f2352fb260741a208673b97
Morphology with a Null-Interface

We present an integrated architecture for word-level and sentence-level processing in a unification-based paradigm. The core of the system is a CLP implementation of a unification engine for feature structures supporting relational values. In this framework an HPSG-style grammar is implemented. Word-level processing uses X2MorF, a morphological component based on an extended version of two-level morphology. This component is tightly integrated with the grammar as a relation. The advantage of this approach is that morphology and syntax are kept logically autonomous while at the same time minimizing interface problems.


Introduction
Over the last few years there has 1)eeu a growing interest in computational morphology and phonology. A number of systems have been developed that deal with word-level processing. A widely used approach is finite-state morphology, most notably two-level morphology (for an introduction, see Sproat 92). Morphological components are sueeessflflly used for a wide range of stand-alone applications like sl)elling correction aM hyphenation. One obvious application is the use in NI,P systems geared to the analysis/generation of text. Surprisingly, they have not been widely al)l)lied in this domain up to now.
A major reason for this is the llrolllem of interfacing morphology with syntax. Reflecting tile current trend in syntax towards lexicalism, unification-1)ased systems use highly structured feature structures as inI)ut. Translating tile output of morphologieM components into such it rel)resentation has proved to be diiticult. Reducing interface problems is therefore crucial to success. *Financial support for the Austrian Research Institute for Artificial Intelligence is provkled by the Austrian Ministry o] Science and Research. We wouhl like to thank Wolfgang lleinz for vMuable comments and suggestimls A tight integration between word and sentence level processing also has linguistic advantages. The boundary between morphology and syntax is fuzzy. When processing written text the units nmrl>hology has to deal with are, ill it tech-nicM sense, not words Mt character strings separated by delimiters. While these strings roughly correspond to the words of a sentence there are problematic cases. In German, e.g., zu-infinitive or w'rbs with separMfie prefixes ;Lre written as a single unit in some instances and separately ill others.
The harder probhml is the integration of morphol)honology which is traditionally formalized in it way not easily t,':mshmdlle into the fei~ture formalisnx. We will show how this can he achieved by merging the word-level grammar of X2MolI.I,' into an lll'S(;-styl0 gralnnla.r, alld by adopting a relational view of its two-level rules. 1l, this llal)or we ass/lille basic flmfilhu'ity with unification-ha.seal N I,P techniques and two-low~l lnorphology.

terprise.
ItPSG differentiates between three strata---PIION, SYNSEM and DTItS. Though morphology is not considered in the standard approach, it suggests itself to be included as a fourth stratum by introducing a feature MORPH into the type sign. Morphotactics are easily described in terms of a feature based grammar. The problem is how to deal with morphophonology. Two proposals have been made to overcome this problem.
Krieger et al. 93 encode finite state automata directly in the feature formalism. Since two-level rules can be compiled into such automata, roof phophonology can be straightforwardly integrate<l into the grammar. While this is formally elegant it seems to be no good solution for practical considerations. First, it is not entirely clear frmn their paper how the problem of null characters can be handled. Second, encoding large automata will result in a very large and unwieldy type hierarchy. In general, introducing automata into feature structures and encoding morphophonology directly at that level seems to be too low-level.
Bird & Klein 93 argue against the use of two-level morphology because of linguistic considerations. The linguistic background of twolevel rules--main stream segmental phonology-has widely been rejected as a valid linguistic model. Instead, they base their implementation on autosegmental phonology (of. Goldsmith 90). This is certainly linguistically appealing. But there are reasons for sticking to a more conservative approach. Finite-state morphology as a formalism is not necessarily tied to segmental phonology. There are various approaches to cope with non-concatenative phenomena--one of tlmm X2MoltF (Trost 90). Also, for a nmnber of languages complete sets of two-level rules do exist and can immediately be brought to bear. Finally, finite-state morphology has proven to be eflicient while the method proposed by Bird ~: Klein 93 seems to be computationally costly.
Like the other apl>roaches ours is also based on IIPSG. Itowever, we employ a different approach to integration. Our grammar is encoded using a unification engine based on constraint logic programming (CLP). Besides conventional attril)utevalue descriptions this system allows for the direct representation of more general relations, as they are required by IIPSG. This extension of the formalism is used for the integration of morl>hology. Thus X2MoI~F is treated as one special relation of tile grammar. As a result, our approach is more modular than the others. While being fully integrated morphology can still be viewed as an autonomous component leading to a more llexible design.
We will now give an overview of X2MolIF hefore describing the integrated system and its implementation in detail.

Word Level Processing X2MoRF
X2MoRF differs fi'mn standard two-level mor-l>hology hi two hnportant respects. Continuation classes are replaced by a feature-based word grammar. This allows for a more line-grained description of morphs. It is also a prerequisite for a tight integration with a unification-based grammar. X2MoRF uses a morph lexicon where each morl>h has one or more feature structures assigned. The word grammar itself is shnple. Morphs have a functor-argument structure along the lines of di Sciullo ,~: Williams 87. Affixes are unary functors while stems are arguments without ally further structure, resulting in a hinary tree structure.
Tile othe,' extension concerns the two-level rules, which are supplemented with a morphological filter consisti,g of a feature structure. This is hnportant because in morl~hol>honology only some rules are purely l)honologically nmtivated. Others are triggered by a mixture of phonologicM and morphological facts. Such rules cannot be properly represented in tile standard al>proach. TAD,, e.g., umlaut an<l schwa epenthesis in (lerman: The third I>erson singular present tense suffix for (;er,nan w~rbs is 4, e.g., sag-t --+ sagt. For stems ending in a dental, schwa is inserted befi)re the ending, e.g., bad-t -, badct. This rule does not hold across the whole vocabulary though.
The th,'ee miles I shown in Fig. lItogether with the a.pl)ropriate entries in the morl>h lexicon (el. Fig. 7 below)--produce the re<luired behavior. In particular, these rules relate surface Nit to lexical $rAt÷t$ 2. X2Mold ' can be seen as a re-*These rules as well as other data presented in the e×: amples are simplified for the purl)ose of denmnstration 2The lexical character A may have the surface realiza-

Implementing HPSG in a CLP Framework
IIPSG employs strongly typed feature structures together with principles constraining them further.
Well-typcdness requirements restrict the space of valid feature structures (cf. Carl)enter 92): Every feature structure must I)e associated with a type, and every type restricts its associated feature structure in that only certain features are allowed and the values of these features must be of a certain type. Appropriateness and value restrictions are inherited along the type hierarchy. The second source of constraints, in order to admit only linguistically valid feature structures, are the principles of grammar. Pollard ,~ Sag 87 allow general implicative and negative constraints in the form of conditional feature structures. In Pollard h Sag in press principles are given only in verbal form. Recent work on formalizing the basis of IIPSG models them as constraints attached to types (e.g., Carpenter et al. 91). Iiowever, these distinctions affect only how the applicability of a principle is specified. More iml)ortant for our present purpose is the form which the constraints expressed by a principle may take. Besides constraints enforcing simple structure sharing (e.g., the Head Featnre Principle given in Fig.2) there are also complex relational dependencies (e.g., in the Subcategorization Principlea). Constraints tions a and d. The rule ha.s an empty phonological context but a morphological filter. This is an example for the treatmeat of non-concatenative phenomena in X2MonF.
3,in a headed phrase (i.e., a phrmsal sign whose DTRS value is of sort head-struc), the suncAT value of the head like these go beyond the exl)ressivity of l)ure Dature formalisms alone and need to be defined in a recursive manner. In order to integrate such complex constraints in the feature unification framework we interpret unitication of typed feature structures under the restrictions of princil)led constra.ints as constraint solving in the CLI' paradigm (Jafl'ar ,~ Lassez g7).
In CI,P the notion of unification is replaced by the more general notion of constraint solving. Constraint solvers may be embedded into a logic l)rogramufing language either by writing a ntetaitlterl)reter or by urn.king use of a system which allows [or the impletn(mtation el + unification ON-tollS]OilS. The s~,cond approacls is taken by I)MCAI (:l,l)4 (l[olzbaur 92), it l)rolog system whose unitication mechanlsnl is extended in such a way that the user may introduce interl)reted terms and specify their meaning with regard to uni[ication through l'rolog predicates. The basic mechanism to a chiow, this behavior is the use of attributed variables, which may l)e qualified by ar-1)itrary user-defined attributes. Attributed variables behave like ordinary l)rolog variables with two notal)le exceptions: when an attributed variable is to be unified with a non-wu'iable term or another attril)uted variable the unifi('.atk)n extensions come into play. For either case the user has to supply a predicate which explicitly specifies how the attril)utes interact and how they should 1)e interpreted with respect to the semantics of the al)l)lication domain. Unilication succeeds only if these constraint solving clauses managing the cond)inati,m -el' vm'ification--af the involved attril)utes are successfid.
The iml)hm~entati(m of typed feature structures in our system makes use of the CLP facilities provided by this enhanced Prolog system. Feature structures are imlflemented by the attril)ute daughter is the concatenation of the phrase's SUBCAT llst with tile list (in order of incre~Lslng obliqueness) of SYNSEM values of the COml)hmlent daughters."(Pollard & .gag in I)ress) 4 I)MC, AI CLP is au enhanced version of SICStus Prolog, awdlahle by anonymous ftp from f tp. ai.univie, ac. at :fs (Type, Dag, Goals), where Dag is a list of featurevalue pairs (which is empty in case of atomic types) or a marker indicating uninstantiatedness of the substructure (feature structures are instantiated lazily). Goals is a list of delayed constraints (see below). Well-typed unification of two feature structures is implemented via the constraint solving clauses mentioned above, taking into account type hierarchy and feature appropriateness (for a detailed description cf. Matiasek & Ileinz 93).
Constraints imposed onto feature structures by the principles of grammar are stated in a conditional form where the antecedent is restricted to contain only typing requirements. 5 In order to account for these conditional constraints we adopt a licensing view: Every node of a feature structure has to be licensed by all principles of grammar.
A node is licensed by a principle if either (i) the feature structure F rooted in that node satisfies the applicability conditions of the l)rinciple and the constraints expressed by the l)rinciple successfully unify with F, or (ii) the feature structure F rooted in that node is incompatible with the applicability conditions of the principle. The interesting case arises when a feature structure does not satisfy the applicability conditions of the l)rinciple but is compatible with them. Thus applicability of tile principle can be decided only later, after further instantiation or unification steps have restricted the (sub)structure rooted at that node. In precisely this case the application (or the al)andoning) of the constraint has to be delayed. The delay mechanism utilizes tim Goals slot in the fs/3 6 attribute, which is dedicated to hold the delayed constraints. As an example take the well known Ilead Feature Principle of IIPSG (Fig.2) r. The conditional operator ===> is translated at read time via terra_expansion/2 and implements the delay mechanism by coml)iling l>recon<lition checks into the principle. These antecedent checks trigger either the application of the princiltle, its abandomnent, or its delay (by annotating the variables wlfich are not sufficiently constrained to decide on the antecedent with the delayed goals).
Two advantages of this approach to implement SThis is only a syntactic variant of attaching constraints solely to types (Carpenter et al. 91) and does not permit general conditional structnres ms used in Pollard & Sag 87. 6pred/n is the usual notation for a n-ary Prolog predicate.
VThe operators ::,,, : :, :, === are defined for typing of a node, path restriction, path concatenation aim value restriction (type or coreference) respectively.  principled constraints are especially important for our present purpose: First, stating redundant typing re<luirements for embedded structures (i.e. type restrictions that would follow automatically from well-typing) forces delay of the conditional constraint until these sul)structures are instantiated. This device can, e.g., be used to block in: finite recursion in recursively detlned constraints. Second, the right hand part of the conditional is not restricted to feature logical expressions, but instead can contain arbitrary Prolog goals. In this way constraints involving relational dependencies (such as the Subcategorization Principle and the morl>hological relation between a lexical and a surface string) can be expressed within the feature fornmlism and there is no need for external devices controllh~g this interaction. Furthermore, the conditional constraint syntax is not restricted to unary licensing principles but can also be used to express relations, such as *s_append/3--needed for implementing the Subcat l~rinciple--which ap-l>ends two feature structure lists (Fig. 3). Note fs_append(X,Y,Z) :-fs_empty appond(X,Y,Z), fs nonempty append(X,Y,Z). fs_empty append(X,Y,Z) :- :-X::=nelist ===> X::first===F, Z::first===F, X::rest===XRest, Z::rest===ZRest, fs_append(XRest,Y,ZRest).  finite loops due to uninstantiated variM)les can never occur, a cruciM requirement when integr;tting relational dependencies into st lazy instantiating feature formalism.

Embedding X2MouF into the Feature System
Originally X2MoItF was realized ~ts st separate morphological component interfaced to the sentence analyzer/generator only via seq.ential (lat~ transfer. In the case. of analysis, the feature strm> ture representing the word form was transmitted to the parser. For generation, X2MoRF' expected a feature structure as inlmt reproducing one or more word forms. This l)urely sequential architecture was not satisfactory lmcauso, of the l)roblems mentioned in the introduction. In order to achieve tight integration, we a(h|l)t a relational view of X2MoM;' and encode the relation between surfiLce string and lexical string <lireetly without using finite state automata (for arguments suI)porting this ai)pro~Lch of. A1)ramson 92). Ilowever, our al)l)roach extends A1)ramson 92 in that it (i) explicitly accounts for the insertion of null characters and (ii) introduces the filter concept of X2MoltF into the relational approach.
The general format of a two-hwel rule sl)eciIication in our system is LCon <=> Transition <=> RCon [:-Filter] in the case of equiwdence rules, option:d rules are written using only single arrows (=> and <=).
These rules aro cmnpiled into Prolog c]a,uses 8 re- buting the ]oxical and surfaco character streams appropriately (see Fig.,1 for an example of the lelision rtlle f'or (]erlllatl).
q'-obtain a c.rroct relathmship between surfa, c(, and h~xi('al string ewwy transition has to be licensed I)y st morphological rule. Transitions not mentioned by rules are handled by a defitult rule. Instantiation of contexts may not be done by the rules themselw,s, since this would make it impos~ sible to obt~dn negation via the cut-operator. Instead, it is handled Sel)a.rately in a backtrackable f~shion.
The central relation is the morphology predicate, (soe l"iI';. 5) nledia.tiug between lexical string, surf:we string (with inserted n.ll elements), the puro (dellullifiod) surl~w(~ string and the feature structure of the morl)hologica.l sign. lnstantiation of pairs is done del)onding on the possible lexical con|in,rations (the lexicon bei,g represented by a trie-structure). The amount oflookahead is detormilmd by the current pair which is to be licensed by morphrule. '~ Synchronization of s,rface and lexical string by insertion of mill characters is also ha.lMlml a.t the insta.ntiatlon hwel.
Tim intogra.tion (ff tim two-hwel rohU, ion into 9This interactio, and the lexicon look,p of the feature structure corresponding to the current morph, which takes pl;~.(:e whell (:llCOllllt(~l'illg ;k IIIOl'ph bOlll/dAry iS not .'4hOWlI for the sake of simplMty. the general framework of the feature based sentence-level and word-level grammars is now performed by adding this relation as a principled constraint at the appropriate level. In a definite clause style AVM notation this could be written as follows (given that morpho:l.ogy/a is a wrapper around the morphology relation given above, starting with empty left context and hiding the nullified surface stream): The actual imi)lementation as a princil)led constraint in our formalism additionally takes care of delaying the actual enforcement of this relation in case the strings are not sufficiently instantiated.
A second provision has to be made in the word level grammar to assnre prol)er concatenation of the lexical strings of the morl)hological signs being combined. Given the subtyping of resign into marg and mfunctor, which in turn has the suhtypes leftfunctor and rightfunctor, the principled constraints ensuring concatenation of a left functor with its argument are shown in  As an example we demonstrate how these constraints interact in forming the third person singular present tense form of the German verb raten (to guess). The lexical string is composed of the stem rat and the suffix +t. The lexical entries of these two morphs are given in Fig. 7.
The two-level rules applicable for this examl)le are the t-elision rule (Fig.4) and two rules with filters licensing a-umlavt and epenthesis, given in Fignre 7: Lexical entries the input notation for our system (Fig.8). lnteractkm between syntactic and morphological processes takes place at the word level. The apl)lieation of the two-lew'J rules relating the surface string (i.e the pllON-value of the word) and the lexic:d-string (i.e. MORP,IMsTRINC ) is also triggered here. This interaction is completely neutral with respect to the direction of l)rocessing due to its relational nature. Parsing is performed by simply instantiating the PIION value. Generation can be achieved when MORPIIIMSTRING is present, which in turn is obtained by concatenating the lexical strings of the resigns instantiated by the morph grammar.
As a result of this constraint interaction the structure shown in Fig. 9 Fig. 9). Information on sul)c;d,egorization and semantic content for the word is obtained fi-om the lexeme lexicon using MORPIIIsTNM aS a key. These constraints con> plete the interaction between syntactic and morphological processing at the word-level.

Conclusion
We have presented a fl'amework for" tile tight integration of word level and sentence lew.q processing in a unification-1)ased paradigm. Tile system is built upon a unification engine hnl)lemented in a CLP language supporting types and delhfite relations as l)art of feature descriptions. Using this ex- tended feature formalism, which is indel>en<h,ntly motivated by reqnh'enlents of standard Ill'St;, iL reiml)lementation of X2MoRF was integr,~ted into the grammar as a specialized relation.
This architecture has computational as well as linguistic advantages, integrating morphology and morphophonology directly into the gralnmar is in the spirit of IIPSG, which views gramm:cr as a relation between the I)honological (or gr~qllielnic) form of an utterance and its syntactic/seniantic rel)resentation. This way the treatnmnt of phenomena transcending tile boundary between in()rphology and syntax is also nlade l)ossil)h~.
On the implementation si(h~, the practi('al problems of interfacing two inherently difl'erent modules are eliminated. For applh:ations this means that using a morl)hological component is made easy. Nevertheless, this tight integration still leaves morphology and syntaz/somantics as autonomous comI)onents, enal)]ing direct use ,)1' existing data sets descril)ing morphopholmh)gy in terms of the two-level p,~ra(ligm.