{'fraction_non_alphanumeric': 0.04305978056533479, 'fraction_numerical': 0.009946337628601701, 'mean_word_length': 4.307332293291732, 'pattern_counts': {'":': 1, '<': 14, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 46, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Abstract Machine for Unification Grammars

This work describes the design and implementation of an abstract machine, Amalia, for the linguistic formalism ALE, which is based on typed feature structures. This formalism is one of the most widely accepted in computational linguistics and has been used for designing grammars in various linguistic theories, most notably HPSG. Amalia is composed of data structures and a set of instructions, augmented by a compiler from the grammatical formalism to the abstract instructions, and a (portable) interpreter of the abstract instructions. The effect of each instruction is defined using a low-level language that can be executed on ordinary hardware. The advantages of the abstract machine approach are twofold. From a theoretical point of view, the abstract machine gives a well-defined operational semantics to the grammatical formalism. This ensures that grammars specified using our system are endowed with well defined meaning. It enables, for example, to formally verify the correctness of a compiler for HPSG, given an independent definition. From a practical point of view, Amalia is the first system that employs a direct compilation scheme for unification grammars that are based on typed feature structures. The use of amalia results in a much improved performance over existing systems. In order to test the machine on a realistic application, we have developed a small-scale, HPSG-based grammar for a fragment of the Hebrew language, using Amalia as the development platform. This is the first application of HPSG to a Semitic language.


Motivation
Research in linguistics has traditionally been aimed at describing the structure of Natural Languages (NLs). Since the 1950s, however, the focus has shifted from attempts to provide such descriptions to the definition of the right way in which to stipulate them. During the past few decades many such formalisms were devised. A 'good' model, according to Shieber (1986), is linguistically felicitous, expressive and computationally effective. It must be powerful enough to capture the wealth and diversity of NLs, yet it must be computationally tractable to allow for computational processing.
Contemporary linguistic formalisms such as LFG (Kaplan and Bresnan, 1982) or HPSG (Pollard and Sag, 1994) have become so rigorous that it is now possible to view them as very high level declarative programming languages. In this metaphor a grammar for a natural language, formally specified using one of the modern frameworks described above, can be viewed as a program. The execution of a grammar on an input sentence yields an output which represents the sentence's structure. This view enables the application of various methods and techniques that were proved useful for programming languages to the study of natural languages.
Historically, many computational fields of research originated from the study of natural languages: important aspects the theory of formal languages are due to Chomsky, for example; and more recently, Prolog originated out of an attempt to provide a language for description of natural languages. Today, however, much progress was achieved in the area of programming languages. Tools and techniques were developed that enable efficient processing of such languages and, more importantly, formal propositions to be made and proved over languages in general and specific programs in particular. These advances are now being incorporated into the realm of natural languages. Grammars for natural languages are specified more precisely; their properties can be mathematically stated; and their processing becomes more efficient. For a survey of some such approaches, see (Shieber, 1986); for examples of the advantages of regarding natural language formalisms as programming languages, see (Barton, Berwick, and Ristad, 1987;Manaster-Ramer, 1987).
This work introduces such an application: an implementation technique that is common for logic programming languages, namely the use of an abstract machine, is applied to (a subset of) the ALE formalism (Carpenter, 1992a), originally designed for specifying feature-structure based phrase-structure grammars. Abstract machines were used for processing procedural and functional languages, but they gained much popularity for logic programming languages since the introduction of the Warren Abstract Machine (WAM -see (Warren, 1983) and a tutorial in (Aït-Kaci, 1991)). Most current implementations of Prolog, as well as other logic languages, are based on abstract machines. The incorporation of such techniques usually leads to very efficient compilers in terms of both space and time requirements.
AMALIA is an abstract machine, specifically tailored for processing ALE grammars. It is composed of data structures and a set of instructions, augmented by a compiler from the grammatical formalism to the abstract instructions, and a (portable) interpreter of the abstract instructions.
The effect of each instruction is defined using a low-level language that can be executed on ordinary hardware. The advantages of the abstract machine approach are twofold. From a theoretical point of view, the abstract machine gives a well-defined operational semantics to the grammatical formalism. This ensures that grammars specified using our system are endowed with well defined meaning. It enables, for example, to formally verify the correctness of a compiler for HPSG, given an independent definition. From a practical point of view, AMALIA is the first system that employs a direct compilation scheme for unification grammars that are based on typed feature structures. The use of AMALIA results in a much improved performance over existing systems (in particular, ALE itself).

Grammatical Formalisms
Much of the recent research in computational linguistics has been directed towards defining a good model in which natural languages would be naturally describable. Having its roots in the study of formal languages, this endeavor started with considering the computational power needed for describing natural languages in general; context free grammars were thus ruled out quite early. But even if one did believe that natural language were, indeed, within the scope of context free languages, one had to admit that context free grammars were not the ideal framework in which to develop grammars for the natural languages. It was understood that the weak generation properties of a grammar in a given formalism (i.e., its ability to recognize all and only the sentences of a language) are not sufficient -there is a need in providing syntactic descriptions that cohere with the way linguists capture the language.
The resulting trend in computational linguistics was to use unification-based formalisms to obtain these two goals. While many such frameworks were developed (see (Shieber, 1986) for a good review), some notions are common to most of them. They are all based on a context free skeleton, where non-terminal symbols are replaced with structured, more complex entities; and the basic operation on these structures is unification. Among these frameworks are Functional Unification Grammar (Kay, 1983), Lexical Functional Grammar (Kaplan and Bresnan, 1982), Generalized Phrase-Structure Grammar (Gazdar et al., 1985) and many others.
A unification-based grammar formalism is a meta-language for describing grammars for (natural) languages. The basic entity of such formalisms is the feature structure -a data structure consisting of a set of feature-value pairs. While different frameworks define feature structures differently, they can in general be captured as directed graphs, where the arcs are labeled with feature names and an f -labeled arc connects nodes v and u if and only if the value of the feature f in the feature structure associated with v is the feature structure associated with u. For a good, informal survey of feature structures and their properties refer to Shieber (1986).
Feature structures can be thought of as an extension of first order terms (see (Carpenter, 1991;Aït-Kaci and Podelski, 1993)), where the sub-terms are coded by feature names rather than by positions. They extend first order terms in that they are in general graphs, whereas first order terms are trees, with possibly shared leaves. Hence, a term might be a common part of more than one sub-term. Some grammatical formalisms decorate feature structures with types, or sorts, that can be captured by labels on the nodes of the graph. Feature structures are used by grammatical formalisms to represent linguistic concepts such as words, phrases and sometimes even grammatical rules.
The basic operation on feature structures is unification. Being very much like first-order term unification, this operation combines the information that is encoded by two feature structures and produces a result that contains the unified information, provided that the two arguments don't contain contradicting information. If the arguments are inconsistent, unification is said to fail.
In this work we are mainly concerned with typed feature structures (TFSs), as described in (Carpenter, 1992b). As their name suggests, each such structure has a type, drawn from a pre-defined, partially ordered set of types. The type hierarchy helps the grammar writer to organize linguistic knowledge in a similar way to common knowledge representation languages. The hierarchy is accompanied by an appropriateness specification that associates features with types; for example, the 'case' feature might be defined to be appropriate for feature structures of type 'noun' but not for structures of type 'verb'. Moreover, appropriateness is inherited: if a feature is appropriate for a type t, then it is appropriate for all the sub-types of t as well. This property is reminiscent of object-oriented systems; in particular, multiple inheritance is supported in this framework.
It is important to note that while some of the above-mentioned formalisms were designed as computational frameworks for developing grammars, others were linguistically oriented in the sense that a grammatical theory was encoded within them in one way or another. Obviously, any such formalism defines at least the expressive power of grammars that can be stipulated within it. But many other linguistic considerations and generalizations can be, and actually are, hard-wired into some formalisms.

The Current Role of HPSG
Recently HPSG has become prominent among the various unification-based formalisms. HPSG (Pollard and Sag, 1987;Pollard and Sag, 1994) was developed by Pollard and Sag as a variant of GPSG and Categorial Grammar, but immediately gained a position of a well-founded, promising formalism for the description of natural languages. It incorporates the notion of typed feature structures, where types are partially ordered according to a defined hierarchy, thus enabling very concise, general rules to be stipulated. Much of the information carried by linguistic entities is stored in the lexicon; as a result, grammar rules become few and very general. HPSG defines a set of linguistically plausible schemas, or universal principles, that are said to hold for all natural languages and are part of every grammar. In addition, language specific rules can be specified in any given grammar.
Due to its generality and elegance, HPSG has gained a lot of popularity. It enables the designing of grammars for various, linguistically different, languages: work has been done on HPSG grammars for English, German (Nerbonne, Netter, and Pollard, 1994), French, Japanese (JPSG Working Group, In Preparation), Korean and many other languages (see a bibliography in (Calcagno, Kathol, and Pollard, 1993) and an electronic bibliography in (Müller, 1996)). HPSG principles were used to describe not only the syntax and semantics of languages, but also their morphology (e.g., (Nerbonne, 1992)) and phonology (e.g., (Bird, 1990;Bird, 1992)). It seems that linguists find this kind of typed-feature-structures based formalism, with lexical rules and a small set of very general grammatical rules, very convenient.
In spite of the interest that HPSG invokes, no formal definition of the formalism exists. Both (Pollard and Sag, 1987) and (Pollard and Sag, 1994) are rather linguistically oriented, in the sense that no mathematical definitions are given for the language of HPSG itself. King (1989; gives a logical formalization of Pollard and Sag (1987); it is an attempt to provide a logical framework within which both the elementary entities of HPSG, such as feature structures and types, and the principles and the rules, can be described. While King (1989) encompasses Pollard and Sag (1987) in its entirety, it does not provide a characterization of all possible HPSG grammars, nor does it describe the current formulation of the theory as expressed in Pollard and Sag (1994). A similar drawback can be found in (Pollard and Moshier, 1990): while it gives a denotational semantics for a typed feature structures system, it is not directed specifically towards HPSG, and no formulation of the properties of HPSG grammars is given.
A different work is described in (Carpenter, 1992b); a wide, concise theory of the logic of typed feature structures is presented, with many variations and applications. Carpenter (1992b) serves as the main reference point for any attempt to define such formalisms; however, as it is not concentrated on HPSG per se, no formal definition for it can be found there either.
Not only a denotational semantics for HPSG is required; operational semantics of the formalism is missing, too. While some compilers for HPSG were developed (see section 1.2.4), they all rely on (Pollard and Sag, 1987) and (Pollard and Sag, 1994) as their source for interpreting the formalism, and as we mentioned above, both references are not formal enough. Since HPSG is not defined formally enough, we opted in this work to implement ALE (see below), which is the most common platform for designing HPSG grammars.

Abstract Machine Techniques
High-level programming languages, especially ones with dynamic structures, have always been hard to develop compilers for. A common technique for overcoming the problems involves the notion of an abstract machine. It is a machine that, on one hand, captures the essentials of the high-level language in its architecture and its instruction set, such that a compiler from the source language to the (abstract) machine language becomes relatively simple to design. On the other hand, the architecture must be simple enough for the machine language to be easily interpretable by common, Von-Neumann machine languages. This attitude also enables the design of portable front ends for the compilers: as the machine language is abstract, it can be easily interpreted by different (concrete) machine languages.
The design of such an abstract architecture must be careful enough to compromise the two, usually conflicting, requirements: the closer the machine architecture is to common architectures, the harder it is to develop compilers for it; and on the other hand, if such a machine is too complex, then while a compiler for it is easier to produce, it becomes more complicated to execute its language on normal architectures.
Abstract machines were used for various kinds of languages: they date back to the P-Code for Pascal. Starting from Landin's SECD (Landin, 1964), many compilers for functional languages were designed this way. When logic programming languages appeared, such techniques were applied to them as well. While Prolog has gained a recognition as a practical implementation of the idea of programming in logic, a method for interpreting the declarative logical statements was needed for such an implementation to be well-founded. In 1983 David Warren designed an abstract machine for the execution of Prolog, consisting of a memory architecture and a set of instructions (Warren, 1983;Aït-Kaci, 1991). Even though there were prior attempts to construct both interpreters and compilers for Prolog, it was the Warren Abstract Machine (WAM) that gave Prolog not only a good, efficient compiler, but, perhaps more importantly, an elegant operational semantics.
The WAM consists of an architecture of the machine, augmented by a compiler from Prolog to the instruction set of the abstract machine. The operational semantics of each instruction is defined using a low-level language that can be trivially mapped to any ordinary hardware. In fact, there is even a formal verification of the correctness of the WAM compiler (Russinoff, 1992). The WAM captures in an elegant way the substantial elements of Prolog. First-order term unification is supported by special data structures and instructions of the machine architecture. Several instructions that deal with control issues implement the backtracking mechanism.
The WAM immediately became the starting point for many compiler designs for Prolog. The techniques it delineates serve not only for Prolog proper, but also for constructing compilers for related languages. To list just a few examples, abstract machine techniques were used for a parallel Prolog compiler (Hermenegildo, 1986), for variants of Prolog that use different resolution methods (Swift and Warren, 1993), extend Prolog with types (Beierle and Meyer, 1994) or with record structures (Smolka and Treinen, 1994), and for a general theorem prover (Schumann, 1991). There have even been attempts to construct a methodology for the design of abstract machines for logic programming languages (Kursawe, 1987;Nilsson, 1993).

Processing HPSG
Linguistic formalisms provide means for describing the structure of natural languages; they do not specify methods for determining whether a given string is indeed a member of the language defined by a grammar; nor do they prescribe ways for computing the structure that the grammar assigns to the permissible strings. These tasks are performed by parsing algorithms. Different parsing algorithms exist for various classes of languages, both formal (see (Aho and Ullman, 1972) for a survey) and natural (see, e.g., (Gazdar and Mellish, 1989;Sikkel, 1993;Pereira and Warren, 1983)). In this work we implement a simple chart parsing algorithm; such parsers were first introduced by (Kaplan, 1973;Kay, 1973) and are widely used nowadays.
Various parsers for HPSG have been designed in the past, some of which compile their input grammars into an executable program. The first work is described in (Prudian and Pollard, 1985); it is an implementation of a very early version of HPSG. For instance, most of the features are limited to accommodate only a small set of atomic values. Rules are specified in a way reminiscent of GPSG rules. This work cannot be considered as reflecting HPSG today.
Franz has implemented an HPSG parser in LISP (Franz, 1990). This parser was designed in accord with Pollard and Sag (1987), and doesn't cover the modifications introduced by Pollard and Sag (1994). It is rather limited, for example by allowing only tree-shaped type hierarchies to be defined -no multiple inheritance is permitted. While a specific HPSG grammar for English is a part of this implementation, the system can be used as a framework for developing different grammars. According to Franz's reports, the parser is very slow, even when used on a limited grammar and short inputs: example sentences were parsed in 12-65 seconds.
A different implementation is HPSG-PL (Popowich and Vogel, 1991;Kodric, Popowich, and Vogel, 1992). This system allows more complex type hierarchies to be defined; it enables the definition of grammar rules, principles and lexical rules, and an HPSG grammar for English is supplied, based on Pollard and Sag (1987). It incorporates a chart parser where the parsing algorithm makes specific use of some grammar features (e.g., HEAD-DTR), and thus the stipulation of rules does not involve explicit phrase structure. The grammar is compiled into a Prolog program where each feature structure is transformed to a fixed-arity list. Yet the performance of the parser is rather low: according to (Popowich and Vogel, 1991), simple sentences take 1-25 seconds of CPU time to parse.
Another system that was adapted for HPSG is Unicorn (Gerdemann and Hinrichs, 1988). Originated as a generalization of a Context-Free parser, this system uses Shieber's extension to Earley's algorithm, thus enabling the definition of various augmented context-free grammars. An HPSG grammar was defined in terms of the Unicorn framework, with some divergence from Pollard and Sag (1994), by Russell (1993). The most important aspect in which Unicorn differs from the above mentioned parsers is that it doesn't incorporate a typing system for feature structures at all. This system was not specifically designed with HPSG implementation in mind, and the grammar was not intended to be complete in any sense, as it was used only as part of a more complex project. We have no reports on the results of this parser for HPSG.
It is important to note that HPSG falls naturally into the class of general constraint systems, and thus the problem of providing the correct structure for an input sentence can be naturally reduced to the problem of solving a constraint system. Many general constraint solvers have been developed recently that were used for linguistic applications, including some for which HPSG grammars were designed. A typical representative is ALE (Carpenter, 1992a). Not being specifically designed for HPSG, this system is a general Attribute Logic Engine incorporating a chart parser with a formalism for specifying relations among typed feature structures in a way that enables encoding of HPSG grammars in a very natural manner. In fact, an HPSG grammar for English has been constructed in this framework by Penn (1993) that covers most of Pollard and Sag (1994). Compilation of ALE programs generates a rather efficient Prolog code.
A very similar project is Troll (Gerdemann, 1993). It is a framework for processing typed feature structures, much in the same way as ALE does, albeit with a slightly different underlying theory. As Troll is still in preliminary phases, not much is reported regarding its use. Another work, aiming at covering as many as possible of the extensions to simple unification formalisms, is CUF (Dörre and Dorna, 1993). This system is still under development. Two more general systems that were used for developing HPSG grammars are TFS (Zajac, 1992), which is a general constraint solver, and PROFIT (Erbach, 1994), which simply compiles TFS based specifications to Prolog.

Computational Grammars for Hebrew
The Hebrew language poses some interesting problems for the grammar designer. The Hebrew script 1 is highly ambiguous, a fact that results in many part-of-speech tags for almost every word (Ornan, 1994). Another problem of the script is that short prepositions, articles and conjunctions are usually attached to the words that immediately succeed them, which makes it harder to parse the input sentences. In addition to these two features, the Hebrew morphology is very rich. A noun base form might have over fifteen different derivations, and a verb base form -more than thirty. All these call for some pre-processing of the input to the parser. Disambiguation of the script, as well as morphological analysis, were covered by different works (Bentur, Angel, and Segev, 1992;Choueka and Ne'eman, 1995;Ornan and Katz, 1995); some major decisions have to be taken, including the representation of the Hebrew script and the treatment of morphological analysis. As the current trend is to use constraint-based formalisms for tasks other than syntax and semantics, this is the approach we choose.
At the syntactic level, Hebrew exhibits a rather free constituent order, although many constraints are placed on the order of words within constituents. The use of agreement features in Hebrew is more extensive than, say, English. For example, nouns and adjectives must agree on number, gender and definiteness. Agreement checking becomes more complicated in coordinated constructs (see (Wintner, 1991)) and much thought must be given to the correct treatment of agreement.
There have been some attempts to provide a computational grammar for (the syntax of) the Hebrew language. The first work was done by Cohen (1984), who had written a special software system for performing both the morphological and the syntactic analysis of Hebrew sentences. This work was very preliminary and its coverage was limited. Another preliminary work is described in (Nirenburg and Ben-Asher, 1984): it is a small-scale ATN for Hebrew, capable of recognizing very limited structures. A transformation-based grammar is suggested in (Chayen and Dror, 1976).
Unification-based formalisms were used for developing Hebrew grammars only recently. A very limited experiment was done using PATR-II (Wintner, 1992) but was later extended (Wintner and Ornan, 1991;Wintner and Ornan, 1996) to a reasonable subset of the language, on a more convenient platform: Tomita's LR Parser/Compiler, which is based on LFG. The grammar is capable of recognizing sentences of rather wide variety and complexity, but produces only the syntactic structures of the input sentences. See (Wintner, 1991) for a detailed discussion. A different work along the same lines is (Yizhar, 1993): it uses the same framework but concentrates on the syntax of NPs in Hebrew, employing ideas from different linguistic theories. All in all, no broad-coverage, efficient, concise computational grammar for Hebrew exists.

Achievements of the Thesis
The main objective of this work was to formally define an operational semantics for a unificationbased grammar formalism, suitable for specifying HPSG grammars, through the use of an abstract machine. To this end we have first conducted a theoretical investigation into the properties of such formalisms. The main contributions of this endeavor are: • Formalization and explication of the notion of multi-rooted feature structures (MRSs) that are used implicitly in the computational linguistics literature; • Concise definitions of a TFS-based linguistic formalism, based on abstract MRSs; • Algebraic specification of a parsing step operator, T G,w , that induces algebraic semantics for this formalism; • Treatment of parsing as a model for computation, assigning operational semantics to the linguistic formalism; • Specification and correctness proofs for parsing in this framework; • A new definition for off-line parsability, less strict than the existing one, and termination proof for off-line parsable grammars.
This more theoretical work was presented as (Wintner and Francez, 1995b). The off-line parsability result is presented in (Wintner and Francez, to appear). Once the theoretical background was set, we have designed AMALIA, an abstract machine for unification-based grammars. This is the first application of abstract machine techniques to a linguistic formalism. The core engine of the machine was presented in (Wintner and Francez, 1995a), and a more detailed presentation is in preparation. The machine is accompanied by a compiler from the ALE specification language to the machine instructions, an interpreter for the machine instructions and a debugger for machine language programs. The abstract machine endows natural language grammars with an operational meaning; furthermore, its use results in highly efficient processing: the compiled grammars are executed much faster than with the existing ALE processor. Some tests we have conducted showed a speed-up of a factor of 20 in compilation time, and a factor of 5-15 in execution time.
In order to test the machine on a realistic application, we have developed a small-scale, HPSGbased grammar for a fragment of the Hebrew language, using AMALIA as the development platform. This is the first application of HPSG to a Semitic language.
Another track of research we are exploring (with Evgeniy Gabrilovich) is the adaptation of AMALIA to perform natural language generation, as opposed to parsing. Based upon the algorithm of (Samuelsson, 1995), a characterization of generation with unification based grammars can be found in (Gabrilovich, In preparation). A separate compiler is constructed, based upon AMALIA's compiler, that transforms a grammar to an inverted, normalized form, more suited for generation. To execute the inverted grammar on AMALIA, very few modifications in the machine are needed. Once this project is completed, AMALIA will become a unified framework for processing grammars, supporting both parsing and generation.

Structure of this Document
In chapter 2 a theory of parsing with typed feature structures is presented. We start in a survey of the theory of TFSs, along the lines of Carpenter (1992b), but we extend it to multi-rooted structures in section 2.7. In particular, we discuss the computational properties of TFS-based grammars and show in section 2.10.4 a condition on grammars that guarantees termination of parsing.
Chapter 3 describes the abstract machine itself, starting with its core, aimed at unifying two feature structures. In section 3.3 this engine is enveloped with control structures to accommodate for parsing. We conclude this chapter with a discussion of some implementation details (section 3.5).
Chapter 4 describes the HPSG-based grammar for Hebrew. Conclusions and suggestions for further research are given in chapter 5. Appendix A lists all the machine instructions, and the Hebrew grammar is listed in appendix B.

Parsing with Typed Feature Structures
This chapter provides the theoretical background for the design of the machine: we discuss below the theory of typed feature structures and the details of parsing with grammars that are based upon them. Section 2.1 outlines the theory of TFSs of (Carpenter, 1991;Carpenter, 1992b). We repeat it here in order to make this document as self contained as possible. However, the well-foundedness result (section 2.3) is an original contribution. We deviate from the presentation of Carpenter (1992b) in section 2.4, where we emphasize abstract typed feature structures (AFSs). Encoding the essential information of TFSs, AFSs were introduced by Moshier (1988) but we use a different presentation that is suited for typed feature structures. Unification is defined over AFSs rather than TFSs. Section 2.7 introduces an explicit construct of multi-rooted feature structures (MRSs) that naturally extend TFSs, used to represent phrasal signs as well as grammar rules. Abstraction is extended to MRSs and the mathematical foundations needed for manipulating them is given. The concepts of grammars and the languages they generate are formally defined in section 2.8, and the TFS-based formalism is thus acquired a denotational semantics. In section 2.9 a model for computation, corresponding to bottom-up chart parsing for the formalism, is presented. The TFS-based formalism is thus endowed with an operational semantics. Next, we prove that both semantics coincide. Finally, we discuss the class of grammars for which computations terminate. We give a more relaxed definition for off-line parsability and prove that termination is guaranteed for off-line parsable grammars. The presentation is accompanied by a running example of a grammar and the parsing process it induces.

Theory of Feature Structures
The first part of this section summarizes some preliminary notions along the lines of (Carpenter, 1992b). For the following discussion we fix non-empty, finite, disjoint sets Types and Feats of types and feature names, respectively. We assume that the set Feats is totally ordered. We also fix an infinite set Nodes of nodes, disjoint of Types and Feats, each member of which is decorated by a type from Types through a fixed typing function θ : Nodes → Types. The set Nodes is 'rich' in the sense that for every t ∈ Types, the set {q ∈ Nodes | θ(q) = t} is infinite.
Below, the metavariable T ranges over subsets of types, t -over types, f -over features and q -over nodes. When dealing with partial functions the notation 'F (x) ↓' means that F is defined for the value x and the symbol '↑' means undefinedness. Whenever the result of an application of a partial function is used as an operand, it is meant that the function is defined for its arguments.
Definition 2.1.1 (Type hierarchy) A partial order ⊑ over Types × Types is a type hierarchy (or inheritance hierarchy) if it is bounded complete, i.e., if every up-bounded subset T of Types has a (unique) least upper bound, ⊔T , referred to as the unification of the types in T . If t 1 ⊑ t 2 we say that t 1 subsumes, or is more general than, t 2 ; t 2 is a subtype of (more specific than) t 1 .
Let ⊥ = ⊔∅ be the most general type. Let the most specific type be ⊤ = ⊔Types. If ⊔T = ⊤ we say that T is inconsistent. Let ⊓T = ⊔{t ′ | t ′ ⊑ t for every t ∈ T } be the greatest lower bound of the set T .
Definition 2.1.2 (Feature structures) A (typed) feature structure (TFS) is a directed, connected, labeled graph consisting of a finite, nonempty set of nodes Q ⊆ Nodes, a rootq ∈ Q, and a partial function δ : Q × Feats → Q specifying the arcs such that every node q ∈ Q is accessible fromq.
The nodes of a feature structure are thus labeled by types while the arcs are labeled by feature names. The rootq is a distinguished node from which all other nodes are reachable. A feature structure is of type t when θ(q) = t. When we say that a feature structure A exists we mean that no node of A is typed ⊤.
Let FS be the collection of all feature structures over the given Feats and Types. We use upper-case letters (with or without tags, subscripts etc.) to refer to feature structures. We use Q,q, δ (with the same tags or subscripts) to refer to constituents of feature structures. Note that all feature structures are, by definition, graphs. Some grammatical formalisms used to have a special kind of feature structures, namely atoms; atoms are represented in our framework as nodes with no outgoing edges. For a discussion regarding the implications of such an approach, refer to (Carpenter, 1992b, Chapter 8).
Definition 2.1.3 (Appropriateness) An appropriateness specification over the type hierarchy and the set Feats is a partial function Approp : Feats × Types → Types, such that: i.e., every feature is introduced by some most general type, and is appropriate for all its subtypes; and if the appropriate type for a feature in t 1 is some type t, then the appropriate type of the same feature in t 2 , which is a subtype of t 1 , must be at least as specific as t.
If Approp(f, t)↓ we say that f is appropriate for t and that Approp(f, t) is the appropriate type for the feature f in the type t. The set of features appropriate for some type is ordered (since Feats is ordered).
i.e., if an arc labeled f connects two nodes, then f is appropriate for the type of the source node; and the appropriate type for f in the type of the source node subsumes the type of target node.
Definition 2.1.5 (Total well-typedness) A feature structure is totally well-typed iff it is well typed and for all f ∈ Feats and q ∈ Q, if Approp(f, θ(q))↓ then δ(q, f )↓.
i.e., every feature which is appropriate for the type labeling some node labels an outgoing arc from that node.
Definition 2.1.6 (Appropriateness loops) The appropriateness specification contains a loop if there exist t 1 , t 2 , . . . , t n ∈ Types such that for every i, Definition 2.1.7 (Paths) A path is a finite sequence of feature names, and the set Paths = Feats * is the collection of paths. We use π, α (with or without subscripts) to refer to paths. ǫ is the empty path. The definition of δ is extended to paths in the natural way: The paths of a feature structure A are Π(A) = {π | π ∈ Paths and δ(q A , π)↓}. Definition 2.1.8 (Cycles) A feature structure A = (Q,q, δ) is cyclic if there exist a non-empty path α ∈ Paths and a node q ∈ Q such that δ(q, α) = q. It is acyclic otherwise.
Definition 2.1.9 (Path values) The value of a path π in a feature structure A = (Q,q, δ), denoted by val(A, π), is non-trivial if and only if δ(q, π)↓, in which case it is a feature structure A ′ = (Q ′ ,q ′ , δ ′ ), where: • for every feature f and for every If δ(q, π)↑, val(A, π) is defined to be a single node whose type is ⊤.
Definition 2.1.10 (Reentrancy) A feature structure A is reentrant iff there exist two different paths π 1 , π 2 such that δ(q, π 1 ) = δ(q, π 2 ). In this case the two paths are said to share the same value.

Subsumption
• for every q ∈ Q 1 and for every f such that h associates with every node in Q 1 a node in Q 2 with at least as specific a type; moreover, if an arc labeled f connects q with q ′ , then such an arc connects h(q) with h(q ′ ). If A ⊑ B then every path defined in A is defined in B, and if two paths are reentrant in A they are reentrant in B.

Well-Foundedness of Subsumption
We prove below that subsumption of TFSs is well-founded iff they are acyclic.
Proof: If A is cyclic, there exist a node q ∈ Q and a non-empty path α that δ(q, α) = q. Let π be such that q = δ(q, π), then the infinite set of paths {πα i | i ≥ 0} is contained in Π(A). If Π(A) is infinite then since Q is finite, there exists a node q ∈ Q that δ(q, π i )↓ for an infinite number of different paths π i . Since Feats is finite, the out-degree of every node in Q is finite; hence q must be part of a cycle.

Theorem 2.3.5 Subsumption of TFSs is not well-founded.
Proof: Consider the infinite sequence of TFSs A 0 , A 1 , . . . depicted graphically in figure 2.2. For every i ≥ 0, A i = A i+1 : to see that consider the morphism h that mapsq i+1 toq i and δ i+1 (q, f ) to δ i (h(q), f ) (i.e., the first i + 1 nodes of A i+1 are mapped to the first i + 1 nodes of A i , and the additional node of A i+1 is mapped to the last node of A i ). Thus there exists a decreasing infinite sequence of cyclic TFSs and subsumption is not well-founded.
Theorem 2.3.6 Subsumption of acyclic TFSs is well-founded.
Proof: For every acyclic TFS A, rank(A) is finite and rank(A) ≥ 0. By lemma 2.3.4, if A < B then rank(A) < rank(B). If an infinite decreasing sequence of acyclic TFSs existed, rank would have mapped them to an infinite decreasing subsequence of IN , which is a contradiction. Hence subsumption is well-founded.

Abstract Feature Structures
The essential properties of a feature structure, excluding the identities of its nodes, can be captured by three components: the set of paths, the type that is assigned to every path, and the sets of paths that lead to the same node. In this section we elaborate on ideas presented in (Moshier and Rounds, 1987;Moshier, 1988); in contrast to the approach pursued in (Carpenter, 1992b), we first define abstract feature structures and then show their relation to concrete ones. The representation of graphs as sets of paths is inspired by works on the semantics of concurrent programming languages, and the notion of fusion-closure is due to (Emerson, 1983). Alphabetic variants have exactly the same structure, and corresponding nodes have the same types.
Only the identities of the nodes distinguish them.
Definition 2.4.2 (Abstract feature structures) A pre-abstract feature structure (pre-AFS) is a triple Π, Θ, ≈ , where • Π ⊆ Paths is a non-empty set of paths • Θ : Π → Types is a total function, assigning a type to every path • ≈⊆ Π × Π is a relation specifying reentrancy.
For the reverse direction, consider an AFS A = Π, Θ, ≈ . First construct a 'pseudo-TFS', Conc(A) = (Q,q, δ), that differs from a TFS only in that its nodes are not drawn from the set Nodes. Let Q = {q [π] | [π] ∈ [≈]}, making use of the fact that '≈' is of finite index. Let θ(q [π] ) = Θ(π) for every node -since A is an AFS, Θ respects the equivalence and therefore θ is representative-independent. Letq = q [ǫ] and δ(q [π] , f ) = q [πf ] for every node q [π] and feature f . Since A is fusion-closed, δ is representative-independent. By injecting Q into Nodes, making use of the richness of Nodes, a concrete TFS Conc(A) is obtained, representing the equivalence class of alphabetic variants that can be obtained that way. We abuse the notation Conc(A) in the sequel to refer to this set of alphabetic variants. Figure 2.3 depicts the abstraction of the example feature structure of figure 2.1.
Proof: Select some A ∈ Conc(A ′ ), B ∈ Conc(B ′ ). If A ⊑ B then, by theorem 2.4.5, Abs(A) Abs(B). By the definition of Conc, Abs(A) = A ′ and Abs(B) = B ′ , so that A ′ B ′ . If A ′ B ′ , construct a function h : Q A → Q B as follows: First, let h(q A ) =q B . Then, perform a depth-first search on the graph A and for every node For every node q ∈ Q A , some path π exists that leads fromq A to q and fromq B to h(q). Θ A (π) ⊑ Θ B (π), and therefore θ(q) ⊑ θ(h(q)). Hence h is a subsumption morphism.

Unification
As there exists a one to one correspondence between abstract feature structures and (alphabetic variants of) concrete ones, we define unification directly over AFSs. This leads to a simpler definition that captures the essence of the operation better than the traditional definition. We use the term 'unification' to refer to both the operation and its result.
Definition 2.5.3 (Closure operations) Let Cl be a fusion-closure operation on pre-AFSs: The unification fails if there exists a path π ∈ Π C ′ such that Θ C ′ (π) = ⊤.
Lemma 2.5.6 Eq preserves prefixes and fusions: If A is a prefix-and fusion-closed pre-AFS and A ′ = Eq(A) then A ′ is prefix-and fusion-closed.
Corollary 2.5.7 If A and B are AFSs, then so is A ⊔ B.
Proof: If A and B are AFSs then the pre-AFS C, defined as in 2.5.4, is prefix-closed (since A and B are). Cl(C) is prefix-and fusion-closed, as is Eq(Cl(C)) in which, additionally, ≈ is an equivalence relation. T y(Eq(Cl(C))) is an AFS, since T y only modifies Θ such that it respects the equivalences. C ′ is the smallest AFS that contains Π C and ≈ C . Since Π A and Π B are prefix-closed, so is Π C . However, Π C and ≈ C might not be fusion-closed. This is why Cl is applied to them. As a result of its application, new paths and equivalence classes might be added. By lemma 2.5.5, if a path is added all its prefixes are added, too, so the prefix-closure is preserved. Then, Eq extends ≈ to an equivalence relation, without harming the prefix-and fusion-closure properties (by lemma 2.5.6). Finally, T y sees to it that Θ respects the equivalences.
Proof: Observe that unification is defined using set union (∪) and type unification (⊔) which are commutative. Therefore, the unification is commutative, too.
Lemma 2.5.9 Unification is associative: Proof: as above.
The result of a unification can differ from any of its arguments in three ways: paths that were not present can be added; the types of nodes can become more specific; and reentrancies can be added, that is, the number of equivalence classes of paths can decrease. Consequently, the result of a unification is always more specific than any of its arguments.
, and in any case Θ A (π) ⊑ Θ C (π). Cl and Eq cannot remove paths or equivalences and T y only makes types more specific, and therefore A C ′ .
Suppose A ⊔ B = A and assume toward a contradiction that B A. Then at least one of the following cases holds: TFSs (and therefore AFSs) can be seen as a generalization of first-order terms (FOTs) (see (Carpenter, 1991)). Accordingly, AFS unification resembles FOT unification; however, the notion of substitution that is central to the definition of FOT unification is missing here, and as far as we know, no analog to substitutions in the domain of feature structures was ever presented.

A Linear Representation of Feature Structures
Representing feature structures as either graphs or attribute-value matrices is cumbersome; we now define a linear representation for feature structures, based upon Aït-Kaci's ψ-terms (though the order relation we use is reversed).
Definition 2.6.1 (Arity) The arity of a type t is the number of features appropriate for it, i.e. |{f | Approp(f, t)↓}|.
Note that in every totally well-typed feature structure of type t the number of edges leaving the root is exactly the arity of t. Consequently, we use the term 'arity' for (totally well-typed) feature structures: the arity of a feature structure of type t is defined to be the arity of t.
In order to define the set of well-formed linear terms over Feats and Types, we assume that the feature names are ordered in a fixed order.
Let { i | i is a natural number} be the set of tags.
Definition 2.6.2 (Terms) A term τ of type t is an expression of the form i t(τ 1 , . . . , τ n ) where i is a tag, n ≥ 0 and every τ i is a term of some type.
Definition 2.6.3 (Totally well-typed terms) A term τ = i t(τ 1 , . . . , τ n ) of type t is totally well-typed iff: • t is a type of arity n; • the appropriate features for the type t are f 1 , . . . , f n , in this order; We distinguish tags that appear in terms according to the type they are attached to: if a subterm consists of a tag and the type ⊥, we say that the tag is independent. Otherwise, the tag is dependent. We will henceforth consider only terms for which the following proposition holds: Definition 2.6.4 (Normal terms) A totally well-typed term ψ = i t(τ 1 , . . . , τ n ) is normal iff: • if a tag j appears in ψ then its first (leftmost) occurrence might be dependent. If it appears more than once, its other occurrences are independent.
We use terms to represent feature structures. We define below an algebra over which terms are to be interpreted. The denotation of a normal term is a totally well-typed feature structure.
Definition 2.6.5 (Feature structure algebra) A feature structure algebra is a structure • for each t ∈ Types, t A ⊆ D A and, in particular: Let D G be the domain of all typed feature structures over Types and Feats. The interpretation of t G over this domain is the set of feature structures whose roots have the type t; the interpretation of f G : D G → D G is the function that, given a feature structure A, returns val(A, f ).
We associate a normal term ψ with a totally well-typed feature structure A in the following way: and undefined otherwise; where θ( i ) = t and for every j, if f j is the j-th appropriate feature of the type t, then δ( i , f j ) = q j and q j is the root of the feature structure associated with τ j .
Conversely, associate a feature structure A = (Q,q, δ, θ) with a normal term ψ = i t(τ 1 , . . . , τ n ), where: • n is the number of outgoing edges fromq; • for every j, 1 ≤ j ≤ n, τ j is the term associated with δ(q, f j ) where f j is the j-th appropriate feature of t; • if the tag i occurs elsewhere in τ 1 , . . . , τ n , we replace the term that i depends on with the term ⊥(), making this occurrence of i independent.
To summarize, there is a one-to-one correspondence between totally well-typed feature structures and normal terms.
Note that the tags are only a means of encoding reentrancy in feature structures. Therefore, when displaying a term in which a tag i appears just once in a term, we will sometimes omit the tag for the sake of compactness. Then, we sometimes omit the type of independent tags, which are implicitly typed by ⊥, and display them as tags only.

Multi-rooted Structures
To be able to represent complex linguistic information, such as phrase structure, the notion of feature structures is usually extended. There are two different approaches for representing phrase structure in feature structures: by adding special, designated features to the FSs themselves; or by defining an extended notion of FSs. The first approach is employed by HPSG: special features, such as DTRS (daughters), encode trees in TFSs as lists. This makes it impossible to directly access a particular daughter. Shieber (1992) uses a variant of this approach, where a denumerable set of special features, namely 0, 1, . . . , are added to encode the order of daughters in a tree. In a typed system such as ours, this method would necessitate the addition of special types as well; in general, no bound can be placed on the number of features and types necessary to state rules (see (Carpenter, 1992b, p. 194)).
As a more coherent, mathematically elegant solution, we adopt below the other approach: a new notion of multi-rooted feature structures, suggested by (Sikkel, 1993), is being defined to naturally extend TFSs. These structures provide a means to represent phrasal signs and grammar rules. They are used implicitly in the computational linguistics literature, but to the best of our knowledge no explicit, formal theory of these structures and their properties was formulated before.
Definition 2.7.1 (Multi-rooted structures) A multi-rooted feature structure (MRS) is a pair Q , G where G = Q, δ is a finite, directed, labeled graph consisting of a set Q ⊆ Nodes of nodes and a partial function δ : Q × Feats → Q specifying the arcs, and whereQ is an ordered, (repetition-free) list of distinguished nodes in Q called roots. G is not necessarily connected, but the union of all the nodes reachable from all the roots inQ is required to yield exactly Q. The length of a MRS is the number of its roots, |Q|. λ denotes the empty MRS, where Q = ∅.
Meta-variables σ, ρ range over MRSs, and δ, Q andQ over their constituents. If Q , G is a MRS andq i is a root inQ thenq i naturally induces a feature structure P r( where Q i is the set of nodes reachable fromq i and δ i = δ| Qi . One can view a MRS Q , G as an ordered sequence A 1 , . . . , A n of (not necessarily disjoint) feature structures, where A i = P r(Q, i) for 1 ≤ i ≤ n. Note that such an ordered list of feature structures is not a sequence in the mathematical sense: removing an element from the list may effect the other elements (due to reentrancy among elements). Nevertheless, we can think of a MRS as a sequence where a subsequence is obtained by taking a subsequence of the roots and considering only the feature structures they induce. We use the two views interchangeably. Figure 2.4 depicts a MRS and its view as a sequence of feature structures. The shaded nodes (ordered from left to right) constituteQ.
A MRS is well-typed if all its constituent feature structures are well-typed, and is totally well-typed if all its constituents are. Subsumption is extended to MRSs as follows: We define abstract multi-rooted structures in an analog way to abstract feature structures.
• Θ : Π → Types is a total type-assignment function An abstract multi-rooted structure (AMRS) is a pre-AMRS A for which the following requirements, naturally extending those of AFSs, hold: • ≈ is an equivalence relation with a finite index We use λ to denote the empty AMRS, too, where Ind λ = ∅ and Π λ = ∅ (so that len(λ) = 0). The closure operations Cl and Eq are naturally extended to AMRSs: If A is a pre-AMRS then Cl(A) is the least extension of A that is prefix-and fusion-closed, and Eq(A) is the least extension of A to a pre-AMRS in which ≈ is an equivalence relation. In addition, T y( Ind, Π, Θ, The partial order is extended to AMRSs: In the rest of this chapter we overload the symbol '⊑' so that it denotes subsumption of AMRSs as well as MRSs.
AMRSs, too, can be related to concrete ones in a natural way: It is easy to see that Abs(σ) is an AMRS. In particular, notice that for every i ∈ Ind σ there exists a path π such that (i, π) ∈ Π σ since for every i, δ(q i , ǫ)↓. The reverse operation, Conc, can be defined in a similar manner.
AMRSs are used to represent ordered collections of AFSs. However, due to the possibility of value sharing among the constituents of AMRSs, they are not sequences in the mathematical sense, and the notion of sub-structure has to be defined in order to relate them to AFSs.
A sub-structure of A is obtained by selecting a subsequence of the indices of A and considering the structure they induce. Trivially, this structure is an AMRS. We use A j..k to refer to the sub- The notion of concatenation has to be defined for AMRSs, too. Notice that by definition, concatenated AMRSs cannot share elements between them.
We now extend the definition of unification to AMRSs: we want to allow the unification of two AM RSs, according to a specified set of indices. Therefore, one operand is a pair consisting of an AMRS and a set of indices, specifying some elements of it. The second operand is either an AMRS or an AFS, considered as an AMRS of length 1. Recall that due to reentrancies, other elements of the first AMRS can be affected by this operation. Therefore, the result of the unification is a new AMRS. We refer to AMRS unification as "unification in context" in the sequel to emphasize the effect that the operation might have on elements that are not directly involved in it.
Definition 2.7.6 (Unification of AMRSs) Many of the properties of AFSs, proven in the previous section, hold for AMRSs, too. In particular, if A, B are AMRSs then so is ( The linear representation of TFSs, suggested in section 2.6, is naturally extended to MRSs: a multi-term is a sequence of terms, where the scope of tags is extended to the entire sequence.

Rules and Grammars
We define rules and grammars over a fixed set Words of words (in addition to the fixed sets Feats and Types). We use w to refer to elements of Words, w i to refer to strings over Words. We assume that the lexicon associates with every word w i a set of feature structures Cat(w i ), its category, 1 so we can ignore the terminal words and consider only their categories. The input for the parser, therefore, is a sequence 2 of sets of TFSs rather than a string of words.
We omit the subscript w when it is clear from the context.
Proof: An immediate corollary of the definition.

In addition, every category of a lexical item is a rule (with an empty body). We assume that such categories don't head any other rule.
Notice that the definition supports ǫ-rules, i.e., rules with null bodies.
Definition 2.8.4 (Grammars) A grammar G = (R, A s ) is a finite set of rules R and a start symbol A s that is a TFS.
Figure 2.5 depicts an example grammar (we use AVM notation for this rule; tags such as 1 denote reentrancy). While this example grammar has no linguistic pretensions, it might be viewed as generating simple sentences in which the predicates are headed by transitive and intransitive verbs. The type hierarchy on which the grammar is based is omitted here. A discussion of the methodological status of the start symbol appears later on in this section, prior to the definition of languages.
For the following discussion we fix a particular grammar G = (R, A s ). We define a derivation relation over AMRSs as the basis for defining the language of TFS-based grammars. Checking whether two given AMRSs A and B stand in the derivation relation is accomplished by the following steps: first, an element of A has to be selected; this element has to unify with the head of some rule ρ; then, a sub-structure of B is selected; this substructure has to unify with the body of ρ. All unifications are done in context, so that other components of the AMRSs involved may be affected, too. Moreover, there must be some way to record the effects of successive unifications; to this end, derivation is defined only for pairs of AMRSs that are already "as specific as needed"; that is to say, if the rule adds any information to the AMRSs, this information already has to be recorded in them in order for them to be related by derivation. This is why, in the definition below, we use Initial symbol: Figure 2.5: An example grammar an AMRS R that is at least as specific as some rule ρ, and not ρ itself, to guide the derivation. This is also why the definition requires that all the unifications do not add information. strong derivation is the relation that holds between such AMRSs; another relation, derivation, relaxes that requirement by allowing two AMRSs to be related even if they contain only part of the information that is required for strong derivation to hold. Since elements of AMRSs involve indices that denote their linear position in the sequence of roots, the operation of replacing some element in one AMRS with a sub-structure, whose length might be greater than one, becomes notationally complicated. Conceptually, though, it resembles very much the replacement of some symbol with a sequence of symbols in context-free derivation, or the replacement of the selected goal (that unifies with the head of some rule) with the body of the rule, in Prolog SLD-resolution. One main difference in our definition is that we do not carry substitutions through sequences of derivations; rather, we treat all the pairs in a derivation sequence as if the appropriate substitutions have already been applied to them (recall that members of these pairs are "as specific as needed").
• there exist a rule ρ ∈ R and an AMRS R ⊒ Abs(ρ) (with len(R) = n), such that: • some element of A unifies with the head of R, and some sub-structure of B unifies with the body of R; namely, there exist j ∈ Ind A and i ∈ Ind B such that: Intuitively, A strongly derives B through some AFS A j in A, if some rule ρ ∈ R licenses the derivation. A j is unified with the head of the rule, and if the unification succeeds, the (possibly modified) body of the rule replaces A j in B. The definition is graphically demonstrated in figure 2.6.
Proof: A → B, therefore there exists a rule ρ ∈ R, an AMRS R ⊒ Abs(ρ) and an index j such that A unifies with the head of R, and B is obtained by replacing A j with the body of R. A and B are already "as specific as needed"; thus, since A ′ unifies with its head and B ′ is obtained by replacing the j-th element of A ′ with its body.
Proof: By induction on the derivation sequence and lemma 2.8.6.
Proof: The derivation is obtained by applying first the derivation steps that derive B from A 1...k and then those that derive C from A k+1 . Since A 1...k * → B, A is "as specific as needed" and the application of the derivation steps from A to B does not affect the applicability of the derivations step to C.
Proof: Immediate from the definition of derivation.
There are various definitions in the literature for the language that is defined by a grammar G expressed in a unification-based grammar formalism. For example, (Shieber, 1985;Shieber, 1992) do not include a start symbol in the grammar at all, and define L(G) as the set of strings derivable from some feature structure. In (Shieber, Schabes, and Pereira, 1994) a start symbol is defined (notated goal axiom), and L(G) is defined as the set of strings that are derivable from some generalization of the start symbol, i.e., from some feature structure that subsumes it. (Sikkel, 1993), on the other hand, assumes that a specific feature cat is present in every feature structure (the value of which simulates non-terminals in a context-free "underlying" grammar), and uses this feature to single out the start symbol: L(G) is the set of strings that are derivable from some feature structure in which the cat feature is S (the start symbol of the underlying context-free grammar). A similar definition is given by (Haas, 1989): L(G) is the set of strings derivable from the start symbol, where the start symbol is a constant (that is, an atomic feature structure).
There is a good motivation to employ a start symbol: the grammar writer might want to specify a certain criterion for the permissible strings in the language, for example, that they are all sentences. Moreover, it makes sense to include in the language such strings that are not derived directly by the start symbol, but rather by a TFS that is related to the start symbol. For example, the grammar writer might state that only TFSs with a cat feature valued S are permissible, meaning that every TFS that is subsumed by the start symbol (that is, contains all the information it encodes) is a sentence. However, such a definition prevents the incorporation of subsumption test (see section 2.10.3 below) into the parsing, since the correctness of the computation can not be maintained.
Due to these consideration we chose a relaxed condition on the start symbol in our definition of languages. We define a derivation relation between AMRSs in a way that allows the initial symbol of the grammar to derive a sequence of lexical entries even if the actual (strong) derivation is between a TFS that unifies with the start symbol and a more specific instance of the pre-terminals.
Definition 2.8.11 (Language) The language of a grammar G is L(G) = {w = w 1 · · · w n ∈ Words * | Abs(A s ) ; B for some B ∈ P T w (1, n)}. Figure 2.7 depicts a derivation of the string "John loves her" with respect to the example grammar. The scope of reentrancy tags is limited to one MRS, of course, but we use the same tags across different MRSs to emphasize the flow of information during derivation. This example shows that the sentence "John loves her" is in the language of the example grammar, since the derivation starts with a TFS that is more specific than the initial symbol and ends in a specification of the lexical entries of the sentences' words.

Parsing as Operational Semantics
Parsing is the process of determining whether a given string belongs to the language defined by a given grammar, and assigning a structure to the permissible strings. Various parsing algorithms exist for various classes of grammars. In this section we formalize and explicate some of the notions of (Carpenter, 1992b, chapter 13). We give direct definitions for rules, grammars and languages, based on our new notion of AMRSs. This presentation is more adequate to current TFS-based systems than (Haas, 1989;Shieber, Schabes, and Pereira, 1994), that use first-order terms. Moreover, it does not necessitate special, ad-hoc features and types for encoding trees in TFSs as (Shieber, 1992) does. We don't assume any explicit context-free backbone for the grammars, as do (Kaplan and Bresnan, 1982) or (Sikkel, 1993). The parsing algorithm we describe is a pure bottom-up one that makes use of a chart to record edges. The formalism we presented is aimed at being a platform for specifying grammars in HPSG, which is characterized by employing a few very general rules (or rule schemata); selecting the rules that are applicable in every step of the process requires unification anyhow. Therefore we choose a particular parsing algorithm that does not make use of top down predictions but rather assumes that every rule might be applied in every step. This assumption is realized by initializing the chart with predictive edges for every rule, in every position.
As is well known (see, e.g., (Lloyd, 1987)), the meaning of a logic program P can be specified algebraically as the least fix-point (lfp) of the immediate consequence operator T P of the program. A similar approach can be applied to a context-free grammar G, such that L(G) equals (a projection of) the least fix-point of an analogous immediate derivation operator, T G . Let G = (V, T, P, S) be a context-free grammar.
In a sense, computing the lfp of T G corresponds to computing the language generated by G. Parsing, then, amounts to checking if the input w is in the language. This process induces an inherently inefficient computation: since w is given, it can be used to optimize the computation. This is achieved by defining T G,w , a parsing step operator, which is dependent on the input sentence w. The set of items I has to be extended, too: an item is a triple [i, A, j] where 0 ≤ i, j, ≤ n (n being the length of w) and A ∈ V . Informally, an item [i, A, j] represents the existence of a derivation for the symbol A to a substring of w, namely w i . . . w j . w ∈ L S (G) if and only if [1, S, n] ∈ lf p(T G,w ), so that parsing now amounts to computing the least fixed point of T G,w , which is more efficient, and then checking whether the appropriate item is in the lfp.
We now return to TFS-based formalisms and define T G,w for a TFS-based grammar G, thus providing means for defining the meaning of G. A computation is triggered by some input string of words w = w 1 · · · w n of length n ≥ 0. For the following discussion we fix a particular grammar G = (R, A s ) and a particular input string w of length n. A state of the computation is a set of items, and states are related by a transition relation. The presentation below corresponds to a pure bottom-up parsing algorithm, as it is both simple and efficient.
Definition 2.9.1 (Items) An item is a four-tuple [i, A, j, c], where i, j ∈ IN , i ≤ j, A is an AMRS and c is either Act, in which case the item is active, or Comp, in which case it is complete. Let Items be the collection of all items.
If [i, A, j, c] is an item, we say that A spans the input from position i + 1 to position j (inclusive). A can be seen as a representation of a dotted rule, or edge: during parsing all generated items are such that A is (possibly more specific than) a prefix of some grammar rule. The notion of items usually employs edges that contain entire rules, whereas we only use prefixes of rules. This difference is not essential, and in an actual implementation of a parser that is induced by T G,w , edges indeed include a reference to the rule on which they rely.
In what follows we define T G,w , a parsing operator that corresponds to (bottom-up) chart parsing. However, it is possible to characterize algebraic operators that correspond to other parsing schemas as well.
Definition 2.9.2 Let T G,w : 2 Items → 2 Items be a transformation on sets of items, where for I ∈ Items,x ∈ T G,w (I) iff either Cases 2.1 and 2.2 perform the operation known as completion: 2.1 moves the dot one position along the body of a rule, and 2.2 creates a complete item once the dot reaches the end of the body. Case 2.3 corresponds to the prediction operation, whereas case 2.5 corresponds to scanning. Case 2.4 handles ǫ-rules, i.e., rules with null bodies, and creates complete items that span a null substring of the input sentence. Notice that cases 2.3 and 2.4 are independent of the argument I and therefore add the same items in every application of T G,w . Case 2.5 is also independent of the argument, but is dependent on the input sentence w.
The operator T G,w , on which the algebraic semantics of TFS-based grammars is based, naturally induces an operational semantics for such formalisms: once the operator is shown to be continuous, a computational process that corresponds to the iterative application of T G,w computes the set of items in the least fix-point of the operator. This process can be thought of as an analog of bottom-up, chart-based parsing: the chart is initialized with predictions for every rule in every position (by operation 2.3) and with complete edges for every input word (by operation 2.5). Then, operations 2.1 and 2.2 are used to apply the grammar rules using the chart, in an unspecified order. We prove below that the process is indeed analogous to parsing w with respect to G.
Theorem 2.9.3 T G,w is monotone: if I 1 ⊆ I 2 then T G,w (I 1 ) ⊆ T G,w (I 1 ).
Proof: Suppose I 1 ⊆ I 2 . If x ∈ T G,w (I 1 ) then x was added by one of the five operations; operations 2.3, 2.4 and 2.5 add the same items every time T G,w is applied, and thus x ∈ T G,w (I 2 ), too. If x was added by operation 2.1, then there exist items α, β in I 1 to which this operation applies. Since I 1 ⊆ I 2 , α, β are in I 2 , too, and hence x ∈ T G,w (I 2 ), too. The same applies for operation 2.2. In any case, x ∈ T G,w (I 2 ) and hence T G,w (I 1 ) ⊆ T G,w (I 2 ).
Proof: First, T G,w is monotone. Second, let I = I 0 ⊆ I 1 ⊆ . . . be a chain of items. If x ∈ T G,w ( i≥0 I i ) then there exist α, β ∈ i≥0 I i as required, due to which x is added. Then there exist i, j such that α ∈ I i and β ∈ I j . Let k be the maximum of i, j. Then α, β ∈ I k , x ∈ T G,w (I k ) and hence x ∈ i≥0 T G,w (I i ). If x ∈ i≥0 T G,w (I i ) then there exists some i that x ∈ T G,w (I i ). I i ⊆ i≥0 I i and since T G,w is monotone, T G,w (I i ) ⊆ T G,w ( i≥0 I i ), and hence x ∈ T G,w ( i≥0 I i ). Therefore T G,w is continuous.
Corollary 2.9.5 The least fix-point of T G,w can be obtained by iteratively computing I m+1 = T G,w (I m ), starting from I 0 = ∅ and stopping when a fix-point is reached.
Proof: By Tarski-Knaster theorem, the lfp exists since T G,w is monotone; By Kleene's theorem, since T G,w is continuous, the lfp can be obtained by applying the operator iteratively, starting from ∅.
Definition 2.9.6 (Algebraic meaning) The meaning of a grammar G with respect to an input sentence w is the least fix-point of the operator T G,w .
Definition 2.9.7 (Computation) The w-computation triggered by w ∈ Words * is the infinite sequence of sets of items I i , i ≥ 0, such that I 0 = ∅ and for every m ≥ 0, I m+1 = T G,w (I m ). Notice that we check whether the generated items are unifiable with the initial symbol, in accordance with the definition of languages. If the initial symbol of the grammar is interpreted differently when languages are defined, a corresponding modification has to be made in the condition for success.

Proof of Correctness
In this section we show that parsing, as defined above, is (partially) correct. First, the algorithm is sound: a w-computation succeeds only if w ∈ L(G); second, it is complete: if w ∈ L(G), it triggers a successful w-computation. Computations are not guaranteed to terminate, but we show that termination is assured for a certain subset of the grammars that are off-line parsable. We discuss off-line parsability in section 2.10.4.

Soundness
In what follows we fix a particular w-computation I 0 , I 1 , . . ., triggered by some input w = w 1 · · · w n . Lemma 2.10.1 If [i, A, j, Comp] ∈ I l for some l then len(A) = 1.
Proof: By definition of T G,w , complete items are generated by operations 2.2, 2.3 and 2.4. All these operations add items in which the AMRS is of length 1.
Proof: By induction on l. If l = 0 then I l = ∅ and the proposition holds vacuously. Assume that the proposition holds for every l ′ < l. Suppose that x = [i, A, j, Act] ∈ I l and A = λ. Then x must have been added by operation 2.1 (dot movement). Then Theorem 2.10.3 (Parsing invariant (a)) If [i, A, j, c] ∈ I l and i < j then there exist B ∈ P T w (i + 1, j) and Proof: By induction on l. If l = 0 then I l = ∅ and the proposition holds vacuously. Assume that the proposition holds for every l ′ < l. Suppose that x = [i, A, j, c] ∈ I l . Then x must have been added by one of the operations. Consider each case separately: where there exist α, β ∈ I l−1 as required and and since B α ∈ P T (i α + 1, j α ) and B β ∈ P T (j α + 1, j β ), by lemma 2.8.2 B α · B β ∈ P T (i α + 1, j β ). The cases in which i α = j α or i β = j β are trivial.

scanning:
Theorem 2.10.4 If a computation, triggered by w, is successful, then w ∈ L(G).
Proof: If a computation is successful then there exists some m ≥ 0 such that x = [0, A, n, Comp] ∈ I m where len(A) = 1 and A ⊔ Abs(A s ) = ⊤. By the parsing invariant, A * → A ′ for some A ′ ⊒ B ∈ P T w (1, n). Hence Abs(A s ) ; B and w ∈ L(G).

Completeness
The following theorem shows that one derivation step, licensed by a rule Abs(ρ) of length r, corresponds to r+1 applications of T G,w , starting with an item that predicts the rule and advancing the dot r times, until a complete item for that rule is generated.
Proof: By induction on l, the number of derivation steps from A to A ′ : The scanning operation (2.5) of T G,w adds appropriate items whenever it is applied. Assume that A → D * → B ⊒ P T w (i+1, j) and the proposition holds for D and B. By the induction hypothesis, for every k, 0 < k ≤ len(D), there exists l k such that [i k , C k , j k , Comp] ∈ I l k , where C k ⊑ A k . Suppose that A → D through a rule ρ of length r by expanding A y to D x...x+r−1 . Then the following sequence of items is generated, where for every m, C 1...m ⊑ D x...x+m−1 , and C r ⊑ A y : [i, λ, i, Act] ∈ I 1 by prediction (2.3) [i 1 , C 1 , j 1 , Comp] ∈ I l1 by the induction hypothesis [i, C 1 , j 1 , Act] ∈ I l1 by dot movement (2.1) [i 2 , C 2 , j 2 , Comp] ∈ I l2 by the induction hypothesis [i, C 1...2 , j 2 , Act] ∈ I max(l1,l2) by dot movement (2.1) . . .
[i, C 1...r−1 , j r−1 , Act] ∈ I max(l1,...,lr−1) by dot movement (2.1) [i, C r , j, Comp] ∈ I max(l1,...,lr−1)+1 by completion (2.2) Items are generated by the dot movement (2.1) operation since the conditions for its application obtain: it is easy to see that the indices (i, j) match; in addition, if for some m, C 1...m ⊑ D x...x+m−1 , and for every k, C k ⊑ A k , then there exists C 1...m+1 that is obtained by unifying some R ⊒ Abs(ρ) first with C 1...m and then with C m+1 , such that C 1...m+1 ⊑ D x...x+m as required. Therefore, by induction on m it can be shown that all the items that result from dot movement are indeed generated. Finally, the completion (2.2) operation is applicable and (since A → D) we have C r ⊑ A y .
Theorem 2.10.6 If w ∈ L(G) then the computation triggered by w is successful.
Proof: w ∈ L(G), hence Abs(A s ) ; B, where B ∈ P T w (1, n). Hence there exist A ′ , B ′ such that A ′ ⊔ Abs(A s ) = ⊤, B ′ ⊒ B and A ′ * → B ′ . By the parsing invariant, there exists l such that [0, C, n, Comp] ∈ I l where C ⊑ A ′ . Hence C ⊔ Abs(A s ) = ⊤, and therefore the computation is successful.

Subsumption Check
To assure efficient computation and eliminate redundant items, many parsing algorithms employ a mechanism called subsumption check (see, e.g., (Shieber, 1992;Sikkel, 1993)) to filter out certain generated items. We introduce this mechanism below and show that it doesn't effect the correctness of the computation.
Define a (partial) order over items: [i 1 , A 1 , j 1 , c 1 ] [i 2 , A 2 , j 2 , c 2 ] iff i 1 = i 2 , j 1 = j 2 , c 1 = c 2 and A 1 ⊑ A 2 . Modify the ordering on sets of items as follows: I 1 I 2 iff for every x 1 ∈ I 1 there exists x 2 ∈ I 2 such that x 2 x 1 . Sets of items are no longer ordered by inclusion, but rather by a weaker condition that only requires the existence of a more general item (in the higher set) for every item (in the lower set).
The subsumption filter is realized by modifying T G,w : x ∈ T G,w (I) only if there does not exist any item x ′ ∈ T G,w (I) such that x ′ x. Namely, for all items that span the same substring and have the same status (Act or Comp), only the most general one is preserved across successive applications of T G,w . Given the new ordering of sets of items, it can be shown that this modification does not harm neither monotonicity nor continuity, and hence every computation is guaranteed to reach a least fix-point. Obviously, the soundness of the computation is also maintained. More interestingly, completeness is preserved, too: recall that the parsing invariant (b) states that if A * → A ′ ⊒ B then for every k some item [i k , C k , j k , Comp] is generated such that C k ⊑ A k . Since the subsumption test only leaves out an item if a more general one exists, the invariant still holds and hence the correctness of the computation is guaranteed. Notice that if L(G) would have been defined as the set of strings that are derivable from the start symbol itself, the subsumption check might have removed crucial items, and the computation could cease to be correct.

Termination
It is well-known (see, e.g., (Pereira and Warren, 1983;Johnson, 1988)) that unification-based grammar formalisms are Turing-equivalent, and therefore decidability cannot be guaranteed in the general case. However, for grammars that satisfy a certain restriction, termination of the computation can be proven. We make use of the well-foundedness result (section 2.3) to prove that parsing is terminating for off-line parsable grammars.
Off-line parsability was introduced by (Kaplan and Bresnan, 1982) and adopted by (Pereira and Warren, 1983), according to which "A grammar is off-line parsable if its context-free skeleton is not infinitely ambiguous". As (Johnson, 1988) points out, this restriction (defined in slightly different terms) "ensures that the number of constituent structures that have a given string as their yield is bounded by a computable function of the length of that string". The problem with this definition is demonstrated by (Haas, 1989): "Not every natural unification grammar has a context-free backbone".
A context-free backbone is inherent in LFG, due to the separation of c-structure from f-structure and the explicit demand that the c-structure be context-free. However, this notion is not welldefined in HPSG, where phrase structure is encoded within feature structures (indeed, HPSG itself is not well-defined in the formal language sense). Such a backbone is certainly missing in Categorial Grammar, as there might be infinitely many categories. (Shieber, 1992) generalizes the concept of off-line parsability but doesn't prove that parsing with off-line parsable grammars is terminating. We use an adaptation of his definition below and provide a proof.
To overcome this problem, (Haas, 1989) uses a different restriction: "A grammar is depthbounded if for every L > 0 there is a D > 0 such that every parse tree for a sentential form of L symbols has depth less than D". (Shieber, 1992) generalizes it and we use an adaptation of his definition below.
Definition 2.10.7 (Finite-range decreasing functions) A function F : D → D, where D is a partially-ordered set, is finite-range decreasing (FRD) iff the range of F is finite and for every d ∈ D, F (d) d.
Definition 2.10.8 (Strong off-line parsability) A grammar is strongly off-line parsable iff there exists an FRD-function F from AMRSs to AMRSs (partially ordered by subsumption) such that for every string w and different AMRSs A, B such that A → B, if A → P T w (i + 1, j) and B → P T w (i + 1, j) then F (A) = F (B).
Strong off-line parsability guarantees that any particular sub-string of the input can only be spanned by a finite number of AMRSs: if a grammar is strongly off-line parsable, there can not exist an infinite set S of AMRSs, such that for some 0 ≤ i ≤ j ≤ |w|, s → P T w (i + 1, j) for every s ∈ S. If such a set existed, F would have mapped its elements to the set {F (s) | s ∈ S}. This set is infinite since S is infinite and F doesn't map two different items to the same image, and thus the finite range assumption on F is contradicted.
As (Shieber, 1992) points out, "there are non-off-line-parsable grammars for which termination holds". We use below a more general notion of this restriction: we require that F produce a different output on A and B only if they are incomparable with respect to subsumption. We thereby extend the class of grammars for which parsing is guaranteed to terminate (although there still remain decidable grammars for which even the weaker restriction doesn't hold).
Definition 2.10.9 (Weak off-line parsability) A grammar G is weakly off-line parsable iff there exists an FRD-function F from AMRSs to AMRSs (partially ordered by subsumption) such that for every string w and different AMRSs A, B such that A → B, if A → P T w (i + 1, j), B → P T w (i + 1, j), A ⊑ B and B ⊑ A, then F (A) = F (B).
Clearly, strong off-line parsability implies weak off-line parsability. However, as we show below, the inverse implication does not hold.
We now prove that weakly off-line parsable grammars guarantee termination of parsing in the presence of acyclic AMRSs. We prove that if these conditions hold, only a finite number of different items can be generated during a computation. The main idea is the following: if an infinite number of different items were generated, then an infinite number of different items must span the same sub-string of the input (since the input is fixed and finite). By the parsing invariant, this would mean that an infinite number of AMRSs derive the same sub-string of the input. This, in turn, contradicts the weak off-line parsability constraint.
Theorem 2.10.10 If G is weakly off-line parsable and AMRSs are acyclic then every computation terminates.
Proof: Fix a computation triggered by w of length n. We claim that there is only a finite number of generated items. Observe that the indices that determine the span of items are bounded: 0 ≤ i ≤ j ≤ n. It remains to show that only a finite number of AMRSs are generated. Let x = [i, A, j, c] be a generated item. Suppose another item is generated where only the AMRS is different: x ′ = [i, B, j, c] and A = B. If A ⊑ B, x ′ will not be preserved because of the subsumption test. There is only a finite number of AMRSs A ′ such that A ′ ⊑ A (since subsumption is wellfounded for acyclic AMRSs). Now suppose A ⊑ B and B ⊑ A. By the parsing invariant (a) there exist A ′ , B ′ such that A * → A ′ ∈ P T w (i + 1, j) and B * → B ′ ∈ P T w (i + 1, j). Since G is off-line parsable, F (A) = F (B). Since the range of F is finite, there are only finitely many items with equal span that are pairwise incomparable. Since only a finite number of items can be generated and the computation uses a finite number of operations, the least fix-point is reached within a finite number of steps.
The above proof relies on the well-foundedness of subsumption, and indeed termination of parsing is not guaranteed by weak off-line parsability for grammars based on cyclic TFSs. Obviously, cycles can occur during unification even if the unificands are acyclic. However, it is possible (albeit costly, from a practical point of view) to spot them during parsing. Indeed, many implementations of logic programming languages, as well as of unification-based grammars (e.g., ALE (Carpenter, 1992a)) do not check for cycles. If cyclic TFSs are allowed, the more strict notion of strong off-line parsability is needed. Under the strong condition the above proof is applicable for the case of non-well-founded subsumption as well.
To exemplify the difference between strong and weak off-line parsability, consider a grammar G that contains the following single rule: and the single lexical entry, w 1 , whose category is: This lexical entry can be derived by an infinite number of TFSs: It is easy to see that no FRD-function can distinguish (in pairs) among these TFSs, and hence the grammar is not strongly off-line parsable. The grammar is, however, weakly off-line parsable: since the TFSs that derive each lexical entry form a subsumption chain, the antecedent of the implication in the definition for weak off-line parsability never holds; even trivial functions such as the function that returns the empty TFS for every input are appropriate FRD-functions. Thus parsing is guaranteed to terminate with this grammar. It might be claimed that the example rule is not a part of any grammar for a natural language. It is unclear whether the distinction between weak and strong off-line parsability is relevant when "natural" grammars are concerned. Still, it is important when the formal, mathematical and computational properties of grammars are concerned. We believe that a better understanding of formal properties leads to a better understanding of "natural" grammars as well. Furthermore, what might be seem un-natural today can be common practice in the future.

AMALIA -An Abstract Machine for Linguistic Applications
This chapter details the design and implementation of the abstract machine. Section 3.1 presents the formal language in which specifications are input, including the type hierarchy, the grammar and the lexicon. The machine is explained incrementally: section 3.2 describes its core engine, dedicated to the unification of two feature structures. The engine is enveloped with control structures to accommodate for parsing in section 3.3. Optimizations and extensions are discussed in section 3.4, and the actual implementation of the machine, including some comparative performance analyses, are given in section 3.5.

Type Specification
A program (i.e., a grammar) must specify the type hierarchy and the appropriateness specification. We adopt ALE's syntax (Carpenter, 1992a) for this specification: it is a sequence of statements of the form: t sub [t 1 , t 2 , . . . , t n ] intro [f 1 : r 1 , . . . , f m : r m ].
where t, t 1 , . . . , t n , r 1 , . . . , r m are types, f 1 , . . . , f m are features and n, m ≥ 0. If m = 0, the 'intro' part is omitted. This statement, which is said to characterize t, means that t 1 , . . . , t n are alland the only -(immediate) subtypes of t (i.e., for every i, 1 ≤ i ≤ n, t ⊑ t i ), and that t has the features f 1 , . . . , f m appropriate for it. Moreover, these features are introduced by t, i.e., they are not appropriate for any type t ′ such that t ′ < t. Finally, the statement specifies that Approp(t, f i ) = r i for every i. Each type (except ⊤ and ⊥) must be characterized by exactly one statement. The arity of a type t, Ar(t), is the number of features appropriate for it.
The full subsumption relation is the reflexive transitive closure of the immediate relation determined by the characterization statements. If this relation is not a bounded complete partial order, the specification is rendered invalid. The same is true in case it is not an appropriateness specification.
We use the type hierarchy in figure 3.1 as a running example, where bot stands for ⊥. The type ⊤ is systematically omitted from type specifications.

Rules and Grammars
A grammar consists of a non-empty set of rules and a set of lexical entries which associate a feature structure with every word. Each rule is a sequence of feature structures of length greater than 1, with possible reentrancies among its elements, and a designated (last) element that is the rule's head. The rest of the elements in a rule form its body. We use multi-terms for representing rules and lexical entries; however, we employ a simple description language in which such terms are expressible, compatible to the ALE input language (Carpenter, 1992a).
ALE's description language for feature structures is based on a logical language developed by Kasper and Rounds (1986), extended to accommodate types, where path sharing is replaced by the notion of variables due to Smolka (1988). A TFS is described as a conjunction of specifications that might include its type, its features, along with their values, or a variable (whose name begins with a capitalized letter) that refers to it. Multiple occurrences of the same variable denote reentrancy. The syntax for specifying rules consists of a rule name, the reserved word 'rule', a description for the rule's head, the reserved symbol '===>' and then the elements of the rule's body, each preceded by the reserved word 'cat>'. Lexical items consist of the word itself, the symbol '--->' and a description. ALE's descriptions can include several other features that are not supported by AMALIA, most notably disjunctions and inequations. Refer to Carpenter (1992a) for a formal definition of ALE's input language.
As an example, the specification of the example grammar of figure 2.5 is depicted in figure 3.2 below. Notice that ALE's syntax places the head of rules before the body. Comments are preceeded by '%'.

First-Order Terms vs. Feature Structures
While TFSs resemble first-order terms (FOTs) in many aspects, it is important to note the differences between them. Most importantly, while FOTs are essentially trees, with possibly shared leaves, TFSs are directed graphs, within which variables can occur anywhere. Moreover, our system doesn't rule out cyclic structures, so that infinite terms can be represented, too. Two FOTs are mutually consistent only if they have the same functor and the same arity. TFSs, on the other hand, can be unified even if their types differ (as long as they have a non-degenerate LUB). Moreover, their arity can differ, and the arity of the unification result can be greater than that of %%%********************** Grammar Rules %grammar s_np_vp rule (phrase,cat:s,agr:Agr,sem:(Sem,arg1:SubjSem)) ===> cat> (cat:(n,case:nom),agr:Agr,sem:pred:SubjSem), cat> (cat:v,agr:Agr,sem:Sem).
loves ---> (word,cat:v,agr:(per:third,num:sg),sem:pred:love). any of the unificands. Consequently, many diversions from the original WAM were necessary in our design. In the following sections we try to emphasize the points where such diversions were made. We assume familiarity with basic WAM concepts in this section.

Processing Scheme
AMALIA's engine is designed for unifying two TFSs: a program and a query. Many queries (representing input Natural Language phrases) can be executed with respect to a given program (the grammar of the Natural Language). The program is compiled only once to produce machine instructions. Each query is compiled before its execution; the resulting code is executed prior to the execution of the compiled program. Execution of the instructions, produced by compiling a query, builds a graph representation of the feature structure denoted by the query in the machine's memory. The processing of a program produces code that, during run-time, unifies the feature structure denoted by the program with a query already resident in memory. The result of the unification is a new TFS, represented as a graph in the machine's memory. In what follows we interleave the description of the machine, the TFS language it is designed for and the compilation of programs in this language. In section 3.3, queries are extended to sequences of TFSs, representing input strings, and programs are extended to sets of rules, i.e., grammars.

Memory Representation of Feature Structures
The major operation of AMALIA's engine is feature structure unification; therefore, the major data structure of the machine is aimed at storing feature structures in an efficient way. Following the WAM, we use a global, one-dimensional array of data cells called HEAP. A global register H points to the top element of HEAP. Data cells are tagged: STR cells represent nodes, and store their types, while REF cells represent arcs, and contain the address of their targets. 1 The number of arcs leaving a node of type t is Ar(t), fixed due to total well-typedness. Hence, we can keep the WAM's convention of storing all the outgoing arcs from a node consecutively following the node. Given a type t and a feature f that is appropriate for t, the position of the arc corresponding to f (f -arc) in any TFS of type t can be statically determined; the value of f can be accessed in one step. This is a major difference from the approach presented in (Aït-Kaci and Di Cosmo, 1993); it leads to a more time-efficient system without harming the elegance of the machine design.
Computations performed on the machine involve TFS unification, during which new structures are built on top of the heap and existing structures might be modified. It is important to note that STR cells differ from their WAM analogs in that they can be dereferenced when a type is becoming more specific. In such cases, a chain of REF cells leads to the dereferenced STR cell. Thus, if a TFS is modified, only its STR cell has to be changed in order for all pointers to it to 'feel' the modification automatically. The use of self-referential REF cells is different, too: there are no real (Prolog-like) variables in our system, and such cells stand for features whose values are temporarily unknown.
One cell is required for every node and arc, so for representing a graph of n nodes and m arcs, n + m cells are needed. Of course, during unification nodes can become more specific and a chain of REF cells is added to the count, but the length of such a chain is bounded by the depth of the type hierarchy and path compression during dereferencing cuts it occasionally. As an example, figure 3.3 depicts a possible heap representation of the TFS b (b( 1 d, 1 )

Flattening Feature Structures
Before processing a TFS, its linear representation is transformed to a set of "equations", each having a flat (nesting free) format, using a set of registers {X i } that store addresses of TFSs in memory. A register Reg[j] is associated with each tag j of a normal term (recall that a term is normal only if all its types are tagged). The flattening algorithm is straight-forward and similar to the WAM's. The order of the equations correspond to a depth-first, postorder search of the term, where new registers are allocated for sub-terms before the sub-terms are processed. Figure 3.4 depicts examples of the equations corresponding to two TFSs.
Linear representation: Set of equations

Processing of a Query
When processing an equation of the form X i0 = t(X i1 , X i2 , . . .), representing part of a query, two different kinds of instructions are generated. The first is put node t/n, X i0 , where n = Ar(t).
Then, for every argument X ij , an instruction of the form put arc X i0 , j, X ij is generated. Execution of the put node instruction creates a representation of a node of type t on top of the heap and stores its address in X i0 ; it also increments H to leave space for the arcs of the newly created node. Execution of the subsequent put arc instructions fills this space with REF cells.
In order for put arc to operate correctly, the registers it uses must be initialized. Since only put node sets the registers, one way of ensuring correctness is having all put node instructions executed before any put arc instruction is. Hence, the machine maintains two separate streams of instructions, one for put node and one for put arc, and executes all elements of the first before moving to the other. This compilation scheme is called for by the cyclic character of TFSs: as explained in (Aït-Kaci and Di Cosmo, 1993), the original single-streamed WAM scheme would fail on cyclic terms.
The effect of the two instructions is given in figure 3.5. We use syntax similar to that of (Aït-Kaci, 1991) for describing the effect of instructions; in particular, the arguments of an instruction are listed succeeding its mnemonic. We use '<STR,t>' to denote an STR cell of type t, and '<REF,a>' to denote a REF cell pointing to the address a.  ( 1 d, 1 ),d). When this code is executed (first the put node instructions, then the put arc ones), the resulting representation of the TFS in memory is the one shown above in figure 3.3.   ( 1 d, 1 ),d)

Compilation of the Type Hierarchy
One of the reasons for the efficiency of our implementation is that it performs a major part of the unification during compile-time: the type unification. The WAM's equivalent of this operation is a simple functor and arity comparison. It is due to the nature of a typed system that this check has to be replaced by a more complex computation. Efficient methods were suggested for performing LUB computation at run time, relying on efficient encoding of types (see (Aït-Kaci et al., 1989)). We compute LUBs only once, at compile time, using a simple transitive closure computation. Since type unification adds information by returning the features of the unified type, this operation builds new structures, in our design, that reflect this addition. Moreover, the WAM's special register S is here replaced by a stack. S is used by the WAM to point to the next sub-term to be matched against, but in our design, as the arity of the two terms can differ, there might be a need to hold the addresses of more than one such sub-term. These addresses are stored in the stack (more details and an example are given below). When the type hierarchy is processed, the (full) subsumption relation is computed and checked for bounded-completeness (using a straight-forward implementation of Warshall algorithm (Warshall, 1962)). Then, a table is generated which stores, for every two types t 1 , t 2 , the least upper bound t = t 1 ⊔ t 2 . In addition, this table lists also the arity of t, its features and their "origin": whether they are inherited from t 1 , t 2 , both or none of them. Figure 3.7 graphically depicts the LUB and appropriateness tables generated for the running example type hierarchy.  Out of this table a series of abstract machine language functions are generated. The functions are arranged as a two-dimensional array called unify type, indexed by two types t 1 , t 2 . Each such function receives one parameter, the address of a TFS on the heap. Recall that the machine is designed to unify two feature structures, one of which is part of a program, represented as code, and the other, which is part of the query, already resides on the heap. Each unify type function receives the address of this second unificand as a parameter. When executed, it builds on the heap a skeleton for the unification result: an STR cell of the type t 1 ⊔ t 2 , and a REF cell for each appropriate feature of it.
Consider unify type[t1,t2](addr) where addr is the address of some TFS, A (of type t 2 ), in memory. Let t = t 1 ⊔ t 2 , and let f be some feature appropriate for t. If f is inherited from t 2 only, the value of the REF cell in the skeleton result is simply set to point to the f -arc in A. In this case, a build ref i instruction is generated, where i is the position of the feature f in t 2 . If f is inherited from t 1 only, a self-referential REF cell is created in the result. But an indication that the actual value for this cell is yet to be determined must be recorded. This is done by means of the global stack S, every element of which is a pair <action,addr>, where action is either 'copy' or 'unify'. In the case we describe, the action is 'copy' and the address is that of the REF cell. Thus, the instruction that is generated is build self ref.
If f is appropriate for both t 1 and t 2 , a REF cell with the address of the f -arc in A is created, and a 'unify' cell is pushed onto the stack. The generated instruction is build ref and unify i, where i is the position of f in t. Finally, if f is introduced by t, a VAR cell is created, with t ′ = Approp(t, f ) as its value, by the instruction build var t' (VAR cells are explained in section 3.4.1).
As an example, we list in figure 3.8 the resulting code for the unification the two types a and b of the running example. Since a ⊔ b = c, the first instruction of the function is build str c. For every feature that is appropriate for c an instruction is generated according to the rules described above. Finally, a return instruction completes the function.

unify type[a,b] (b addr)
build str(c); % since a ⊔ b = c build self ref; % the value of f1 is yet unknown. build ref (1); % f2 is the first feature of b, build ref and unify(2); % f3 is the second, and it still % has to be unified with a. build var(bot); % f4 is a new structure. return; This example code is rather complex; often the code is much simpler: for example, when t 2 is subsumed by t 1 , nothing has to be done. As another example, if t 1 is subsumed by t 2 , then only additional features of the program term have to be added to A. For each such feature, a unify feat i instruction is generated, where i is the position of the feature. Another case is when t 1 and t 2 are not compatible: unify type[t1,t2] returns 'fail'. This leads to a call to the function fail, which aborts the unification. 2 The effect of the type unification instructions is given in figure 3.9.
The special purpose register ADDR is used for passing the parameter; the exact details of control transfer mechanisms, including the effect of return, are straight-forward and won't be specified here.

Processing of a Program
The program is stored in a special memory area, the CODE area. Unlike the WAM, in our framework registers that are set by the execution of a query are not helpful when processing a program. The reason is that there is no one-to-one correspondence between the sub-terms of the query and the program, as the arities of the TFSs can differ. The registers are used, but (with the exception of X 1 ) their old values are not retained during execution of the program. Three kinds of machine instructions are generated when processing a program equation of the form X i0 = t(X i1 ,. . . ,X in ). The first one is get structure t/n,X i0 , where n = Ar(t). For each argument X ij of t an instruction of the form unify variable X ij is generated if X ij is first encountered; if it was already encountered, unify value X ij is generated. For example, the machine code that results from compiling the program a( 3 d1, 3 ) is depicted in figure 3.10. The implementation of these three instructions is given in figure 3.11. get_structure a/2,X1 % X1 = a( unify_variable X2 % X2, unify_value X2 % X2) get_structure d1/0,X2 % X2 = d1 The get structure instruction is generated for a TFS A p (of type t) which is associated with a register X i . Execution of this instruction matches A p against a TFS A q that resides in memory, using X i as a pointer to A q . Since A q might have undergone some type inference (for example, due to previous unifications caused by other instructions), the value of X i must first be dereferenced.   The dereferenced value of X i , addr, can either be a self-referential REF cell or an STR cell. In the first case, the TFS has to be built by executing the program. A new TFS is being built on top of the heap (using code similar to that of put structure) with addr set to point to it. For every feature of this structure, a 'copy' item is pushed onto the stack. The second case, in which X i points to an existing TFS of type t ′ , is the more interesting one. An existing TFS has to be unified with a new one whose type is t. Here the pre-compiled unify type[t,t'] is invoked.
To readers familiar with the WAM, the unify variable instruction resembles very much its WAM analog, in the read mode of the latter. There is no equivalent of the WAM's write mode as there are no real variables in our system. However, in unify value there is some similarity to the WAM's modes, where the 'copy' action corresponds to write mode and the 'unify' action to read mode. In this latter case the function unify is called, just like in the WAM. This function (figure 3.12) is based upon unify type. In contrast to unify type, the two TFS arguments of unify reside in memory, and full unification is performed. The first difference is the reason for removing an item from the stack S and using it as a part of the unification process; the second is realized by recursive calls to unify for subgraphs of the unified graphs. Notice that the function returns immediately if its arguments point to the same address, and binds its arguments otherwise. This guarantees correctness even in the face of cyclic structures.
When a sequence of instructions that were generated for some TFS is successfully executed on  ,addr1+i))) then return(false); bind(addr1,addr2); return(true); end;

Parsing
The previous section delineated the core engine of AMALIA; this section shows how it is extended with control instructions to accommodate for parsing. This constitutes the major difference between AMALIA and abstract machines that were devised for variants of Prolog: computations performed on AMALIA amount to parsing with respect to the input grammar, as opposed to SLD resolution.
The parsing process described in section 2.9 above is a generic, abstract one: there is no specification of the order in which new items are computed during each application of T G,w . When designing the control mechanisms of the machine, several parameters have to be explicated and their values determined. In what follows we describe how the machine (and a compiler for it) are designed to allow for efficient implementation of parsing, that is, computation of the least fix-point of T G,w for a given grammar G and an input string of lexical elements w of length n. The control modules of AMALIA are motivated by the abstract process of chart parsing and are not, in general, inspired by the specific TFS-based formalism that we deal with. For example, the machine can also be used for parsing with respect to "plain" context-free grammars.
Notice that cases 2.3, 2.4 and 2.5 of T G,w are independent of the argument I and add the same items in every application of the operator. Therefore, when computing the least fix-point of the operator, they are computed only once, when the process is initiated. Cases 2.1 and 2.2 are more interesting. We treat completion as a special case of dot movement where the dot is moved from the penultimate position to the final one, so that completion can take place immediately after the final application of dot movement. Dot movement creates an item on the basis of two items in I, an active one [l, A, m, Act] and a complete one [m, B, r, Comp], where l ≤ m ≤ r. 3 Since for every off-line parsable grammar the number of items that span a particular substring of the input is finite, it is possible first to generate the items spanning (m, r), for all m > l, and all the items spanning (l, m), where m < r, and only then the items spanning (l, r). This is the invariant underlying our design. When generating items that span (l, r), the active items that span (l, m) are combined with complete items that span (m, r), where m decreases from r − 1 to l. We use a chart to store generated items, since they may be used more than once.

A Parsing Algorithm
A chart of size n is a data structure that can be accessed by a key that is a triple (l, m, r), where 1 ≤ r ≤ n, 0 ≤ l ≤ r − 1 and l ≤ m ≤ r − 1. Given these restrictions, a chart of size n can be accessed by n r=1 r−1 l=0 r−1 m=l 1 = n r=1 r−1 l=0 (r − l) = n r=1 r(r − 1)/2 = (n 3 − n)/6 different keys. Keys are linearly ordered as follows: (l, m, r) ≺ (l ′ , m ′ , r ′ ) iff r < r ′ or ((r = r ′ ) and (l > l ′ )) or ((r = r ′ ) and (l = l ′ ) and (m < m ′ )). Each element of the chart is a pair of chart entries. Such pairs are accessed by the coordinates of the key: the element indexed by (l, m, r) is a pair indexed by (l, m), (m, r) . Additionally, if two elements have matching sub-keys then it is required that the corresponding elements of the pairs be identical: the element indexed by (l, m) in (l, m, r) must be identical to the element indexed by (l, m) in (l, m, r ′ ). Therefore, even though there exist (n 3 − n)/6 different keys by which 2 × (n 3 − n)/6 chart entries can be accessed, there are only n(n + 1)/2 different chart entries.
Each chart entry contains two lists of edges: active and complete. Each list, both active and complete ones, is a sequence of edges along with a specified current edge, on which the following operations are defined: An edge can be either active or complete. An active edge stems from some grammar rule; it contains a part that was already scanned, and a part that is left to be seen. The position between the two parts is indicated by the location of the dot. A complete edge is a result of scanning an entire body of some rule, and constructing the rule's head.
The parsing process is outlined informally in figure 3.13: (a) shows the order in which chart entries are constructed; (b) shows the order in which chart entries are scanned to construct the [left,right] entry; combination of chart entries is performed as described in (c). The heart of the process is dot movement, which creates a new edge e by unifying the TFS that immediately succeeds the dot in an active edge e1 with some complete edge e2.   The last part of the process requires some precaution: application of dot movement to an active edge in (l, m) and a complete one in (m, r) results in a new edge in (l, r). This edge might be complete; in the special case where l = m, the complete edge that is thus created is added to (l, r) = (m, r). Such edges can now be combined with active edges in (l, m) again. Notice that the situation occurs only when l = m. The only way an active edge in the (l, l) entry of the chart (that is, an edge with the dot in the initial position) can become complete is if the rule on which the edge is based is of length 2 (a unit rule). Therefore, for unit rules a special treatment is required: first, active edges that originate from unit rules are placed before edges that stem from other rules within the same chart entry. This guarantees that complete edges that result from application of dot movement on (an active edge that stems from) a unit rule are constructed before they are needed. The only problem left is the possibility of more than one unit edge in the same chart entry. Such rules are required to be ordered by the grammar writer, such that if ρ 1 can "feed" ρ 2 , ρ 1 precedes ρ 2 in the grammar. 4 The advantage of this parsing algorithm is that it is simple; in particular, it does not require an agenda. In the above description we assumed that the chart is initialized with complete edges for the lexical entries of the input words, and with active edges -with the dot in the initial position -for the rules.
Following this informal description, several observations about the parsing process can be made: • After the edges in the [l, r] chart entry are constructed, no more edges will be added to entries that were constructed earlier; • When complete edges of column c are used, no complete edges of columns 1, . . . , c − 1 will be used any more. Consequently, at every point during the process, the complete edges in chart entries whose second index is less than r will not be used any more; • active edges may be used over and over again.
These observations guide the specification of the machine architecture, which is divided into data structures and machine instructions.

Data Structures
The chart is represented as a two-dimensional array, indexed by two integers, where chart[l,r] refers to a chart entry. Each chart entry contains two lists of edges, which are referred to as chart [l,r].active and chart[l,r].complete.
A complete edge is represented in memory as a structure e containing an address, e.addr, of some HEAP cell that is the root of a feature structure. An active edge is represented as a structure containing a pointer, e.label, and a set of register values, e.regs. An active edge always stems from some grammar rule; it records a major part of the state of the machine at some given time. e.label is the address (in CODE) of the first instruction in the code that is generated for the TFS immediately following the dot of the edge; e.regs records the values of the machine registers. The registers represent the part of the edge prior to the dot, whereas the pointer represents the part following it. 5 During a computation of AMALIA, edges are repeatedly stored in the chart and loaded from it. When an edge e is loaded, e.label is used to determine the next instruction that is to be executed; this implies an implicit branch whenever an active edge is loaded (see the effect of the call instruction below). The auxiliary function make edge creates an edge from its components (an address and a set of values for the registers).
Special purpose registers record the current values of the chart indices LEFT, RIGHT and MID and the input length LEN. Like all the machine's data structures, the control structures are initialized before every execution of a program: the registers LEFT, MID, RIGHT and LEN are set to 0 and new is applied to every chart entry. The control structures are affected by the execution of machine instructions that are generated for both the program and the query, as explained below.

Compilation
Compilation of a grammar produces code that, when executed, realizes the parsing process with respect to the grammar and an input query (that is a sequence of TFSs) representing the Natural Language input. In this section we describe the compilation scheme in terms of the resulting code.
First, the chart is initialized. Three sets of edges have to be inserted to the chart, in correspondence to the three cases of T G,w (definition 2.9.2) that are independent of the input: complete edges for lexical items, active edges (with the dot in the initial position) for rules and complete edges for ǫ-rules.
The first set, corresponding to case 2.5 of T G,w , is inserted to the chart by processing the query. Recall that processing a query results in the generation of machine code that is executed prior to the execution of the program code. When the query is composed of more than one feature structure, the generated code contains proceed instructions that are inserted after every feature structure in the query. The effect of proceed is given in figure 3.14; the parameter X i is the register that points to the root of the feature structure that was just created (that is, the first register mentioned in the code that immediately precedes the proceed instruction). Processing Rules of length one (ǫ-rules, or empty categories), corresponding to case 2.4, are processed by the compiler in a special way, that is described in section 3.4.3.
The main product of the compiler is the code that corresponds to dot movement and completion (cases 2.1 and 2.2). For a rule of the form: A 1 , A 2 , . . . , A n ⇒ A 0 the compiler generates the code given in figure 3.16, where r i is the index of the first register that is mentioned in the code for A i , and where X is the first register mentioned in the code for A 0 . The effect of this code is discussed in section 3.3.4.
Controlling the order in which chart entries are constructed is independent of the grammar. Consequently, the compiler generates a few pieces of identical code for every grammar. On the basis of the generated code for one rule, the code for a grammar consisting of k rules is given in figure 3.17.
An important observation regarding the control flow of a compiled program has to be made here. In general it is impossible to determine, during compile time, the order in which machine instructions will be executed. Indeed, some control instructions (in particular, the key manipulation instructions) resemble ordinary conditional branches. However, other instructions (call, copy active edge and copy complete edge) 'hide' implicit branches to addresses that are only known at run time. Further details are given below.  To conclude this section, figure 3.18 depicts (part of) the code that was generated by the compiler for the example grammar of figure 3.2. Lines 2-11 contain the constant, grammar independent code; lines 12-49 list the code that was generated for the first rule; and the code on the right side was generated for the lexical entries of the words "john" and "love".

Effect of the Machine Instructions
This section details the effect of the control module machine instructions. While the effect of each instruction is given independently of its context, we assume throughout the description that a sequence of instructions is present that were generated by the compiler for some grammar.
The instructions first key, next key and check key, constantly generated for every grammar, are aimed at implementing the outermost control flow during parsing. Motivated by the invariant stated in section 3.3.1 above, these instructions form a loop that causes AMALIA to build all the necessary chart entries in the order specified there. The body of the loop contains code whose effect corresponds to the procedure Combine of figure 3.13. The effect of the key-manipulation instructions is depicted in figure 3.19.
Every iteration of the main loop corresponds to the combination of two chart entries, taking the active edges from the entry indexed by the values of LEFT and MID and the complete edges from the entry indexed by the values of MID and RIGHT. To loop over all the active edges (in the designated chart entry), two instructions are used: tst active edges and next active edge. The instructions tst complete edges and next complete edge scan the complete edges in the chart entry that is indexed by the values of MID and RIGHT.
The effect of these four instructions is given in figure 3.20. The two instructions that loop over the active edges are straight-forward; the other two are quite similar, with a few differences. First, tst complete edges initializes the list of complete edges in the [MID,RIGHT] chart entry. Second, next complete edge calls the auxiliary function reset trail, whose purpose will be discussed presently.
put rule L 1 . . . put rule L k first key L start : next key L act : tst active edges L end L comp : tst complete edges L ′ comp load machine state call next complete edge L comp L ′ comp : next active edges L act L end : check key L start end program L 1 : code for 1st rule . . .
L k : code for k-th rule entry. The address in the code area of the next instruction to be executed is stored in e1.label; this code is to be executed on the feature structure pointed to by e2.addr. In other words, the code that was generated for the next element of e1, viewed as a procedure call, is to be executed on the complete edge e2, whose address is viewed as a parameter. call loads the registers' values from e1, and saves e2.label in the special purpose register ADDR, which is used for passing parameters. Then, it saves the address to return to (that is, the address of the instruction following the call) in a special purpose stack of return addresses and branches to e1.label The first instruction that is executed in a 'procedure' is load fs X, which loads the value stored in ADDR onto the register X. Then, the instructions that were generated for this part of the rule are executed in order, thus unifying the TFS immediately after the dot (in the active edge) with the TFS that X r points to. If the unification succeeds, control flows to the copy active edge instruction that adds the newly created MRS to the chart, and returns the control to the address stored in the stack of return addresses. If the entire body of the rule was consumed, the last instruction is copy complete edge (see figure 3.16), which adds the newly created complete edge to the chart and returns. The auxiliary function copy mrs copies the MRS accessible from the current registers on top of the heap. copy fs X copies the feature structure rooted in X on top of the heap. The effect of these three instructions is depicted in figure 3.22.
When the code that is associated with some program feature structure is executed, the heap is modified. Sometimes the same code has to be executed on several TFSs (since one active edge might be combined with several complete ones). If the unification fails, that is, fail is called, the heap must be restored to its original form. To this end a new data structure is introduced: the trail. It is an array whose contents are pairs of the form <address,value>, which record modifications  Consider now the case where some unification fails. The effect of the fail function has to be modified: failure of a "local" unification no longer means termination of the program; rather, it indicates the need to try different edges to combine. Failure can be detected during the execution of any of the instructions in the program code. In this case, the previous bindings are undone, using a call to unwind trail, and the stack is initialized using reset stack. Then, a branch is made to the last tst complete edges instruction executed. This instruction's address is stored in the special purpose register RETURN ADDR. The definition of fail is given in figure 3.23.  The WAM uses a trail to undo 'side effects' on the stack and the heap upon backtracking to a choice point (see (Aït-Kaci, 1991, chapter 4.2)). In AMALIA no backtracking is performed and so the trail could have been eliminated. Notice that after execution of program code, the newly created edge (whether active or complete) is copied onto the heap. A different strategy could have been chosen, in which the active edge is copied prior to the execution of the program code. In this case, all that has to be done upon failure is restoring the value of the heap pointer H, so that the cells that were used by (ineffective) instructions can be re-used. While the gain in this strategy is that no trail is needed, it doesn't seem to be too effective: active edges would have to be copied before they are used, which means that many MRSs will be copied in vain. Since copying is one of the most time-consuming operations, we opt for the method described above.

Lazy Evaluation of Feature Structures
One of the drawbacks of maintaining total structures is that when two TFSs are unified, the values of features that are introduced by the unified type have to be built. For example, unify type[a,b] (figure 3.8) has to build a TFS of type bot, which is the value of the f 4 feature of type c. This To optimize the design in this aspect, a new kind of heap cells, VAR-cells, is introduced. A VAR cell whose contents is a type t stands for the most general TFS of type t. VAR cells are generated by the various unify type functions for introduced features; they are expanded only when the explicit values of such features are needed: either during the execution of get structure, where the dereferenced value is a VAR cell, or during unify. 6 In both cases the TFS has to be built, by means of executing the pre-compiled function build most general fs with the contents of the VAR cell as an argument. This function (which is automatically generated by the type hierarchy compiler) builds a TFS of the designated type on the heap, with VAR cells instead of REF cells for the features. These cells will, again, only be expanded when needed. We thus obtain a lazy evaluation of TFSs that weakly resembles Götz's notion of unfilled feature structures ((Götz, 1994)). Moreover, we gain another important property, namely that our type hierarchies can now contain loops, since appropriateness loops can only cause non termination when introduced features are fully constructed. This approach might not be applicable in the presence of type constraints, which are currently not supported by AMALIA.

Partial Descriptions
AMALIA requires that its input be total: both grammar rules and lexical entries are required to consist of totally well-typed feature structures. This requirement might be problematic for the grammar writer, who might prefer to specify only partial information. To this end, the compiler employs a pre-processor that performs type inference on the partial input; the result of this processing is almost total, but partiality is maintained in certain cases.
Recall that a normal term consists of a tag, a type and a sequence of arguments, each of which is a normal term. Whenever some sub-term is the most general term of its type, it is substituted by the type name only. Using the running example of figure 3.1, the term a(bot, d()) can be replaced by the term a.
When the compiler encounters such a partial description, it creates one of the following two instructions: put var t/n, X i , if the type t is part of a query code, or get var t/n, X i , if it is part of a program code. put var is very similar to put node, with two differences: it creates a VAR-cell, rather than an STR-cell, on the heap; and it does not leave space for REF-cells, as there won't be any. get var is the analog of get structure, but is much simpler: it uses build most general fs to create the most general feature structure of type t on top of the heap, and then calls unify to unify this newly created TFS with the one that is pointed to by X i . Thus, partial descriptions in the input result in a more efficient code, and consequently in a faster, more space-economic processing.

Empty Categories
The presence of empty categories (ǫ-rules) in a grammar causes both theoretical and practical problems. There is a current trend in HPSG of avoiding empty categories altogether, due to theoretical linguistic and cognitive reasons (see, e.g., (Sag and Fodor, 1994)). From a computational point of view, such categories always cause considerable efficiency degradation.
AMALIA is designed to support empty categories as an inherent part of the input grammars. Empty categories are processed by the compiler at compile time. Each category is matched against every element i in the body of every rule r, and if the unification succeeds, a new rule is created: this rule consists of r, modified by the effects of the unification, in which the i-th element is removed. This process can be shown to yield an equivalent grammar, if it terminates.
However, for certain grammars, the process will never terminate, since it can lead to the creation of new empty categories (when it is applied to rules with just one element in their bodies). A typical example would be the rule When it is applied to the empty category elist , a new empty category is created: This new empty category can, in turn, be unified with the head of the rule, etc. To eliminate such infinite loops and to maintain efficiency even in face of empty categories, the compiler limits their application: new rules, that were obtained by applying some empty category to an original grammar rule, can not by applied to other empty categories. This implies that a single grammar rule cannot derive two empty categories. Since usually empty categories are designed to operate in a very limited context, this seems to be a reasonable compromise.

Lexical Ambiguity
The lexicon associates every word w with a set of feature structures Cat(w). If this set contains more than one element, w is said to be ambiguous. AMALIA processes the lexicon at compile time: to every input word w i the lexicon assigns a normal term, which is transformed to machine instructions. If w i is ambiguous the lexicon assigns it several normal terms. The code that is generated for these terms is regular query code; however, the instruction that separates the code of one term from the code of another, if both are associated with the same word, is same word instead of proceed. The only difference between the two instructions is that the former does not increment the value of the special purpose register LEN. At run time, proceed causes the machine to search for the next lexical entry, whereas same word does not. Thus, the execution of the code that was generated for an ambiguous lexical entry w causes several complete edges to be inserted into the chart, one for each element of Cat(w).

Functional Attachments
While the phrase structure grammar organization underlying our design is usually appropriate for constructing grammars for natural languages, there is sometimes need in computations that are not easily expressed using the formalism. Although contemporary grammatical formalisms tend to be highly declarative in nature, grammar writers might find it useful to resort to some mechanism that enables simple computations to be executed without the full power of the grammatical formalism. ALE supports this need to the fullest, by incorporating a complete system of definite clause attachments to grammar rules. Basically, this is a version of a Prolog-like programming language, where the basic units are TFSs rather than FOTs. AMALIA does not include such a module. As a limited solution, we implemented a small set of functions that can be used by the grammar writer; these functions are executed during the parsing process and their results might be integrated with the parsing.
As an example, consider the pre-defined function append. It receives two parameters, which must be lists of TFSs, and returns a list consisting of their concatenation. The grammar writer can use append by integrating it in the grammar: following the body of any rule a goal of the form 'goal> append(L1,L2,L3)' can be placed. The variables L1 and L2 must be associated with lists, and after the goal is executed, the variable L3 will be bound to the concatenation of the input lists. Now, L3 can be used in the head of the rule.
Since parsing is performed bottom-up, goals can only be placed after all the elements of the body of a rule; their input parameters must be instantiated, and the output parameter can only be used in the head of the rule. Currently, only a small number of functions (mainly for handling lists and sets) are integrated into AMALIA, but more can be easily added. It must be noted, though, that this situation is very different from ALE, in which the user can define just any definite clause relation.

Implementation
AMALIA is implemented as a complete grammar development system, containing a compiler from the ALE input language to the abstract machine language, an interpreter for the machine instructions, a simple debugger for the machine language and a graphical user interface (GUI) that eases the process of grammar design and debugging. The major part of the software is written in C; the compiler is written using yacc and lex, and the graphical user interface is implemented using Tcl/Tk (Ousterhout, 1994). The system is implemented on a Sun Sparc station under the Solaris operating system.
The system was tested with a wide variety of grammars, mostly adaptations of existing ALE grammars. It is important to note that AMALIA does not provide the wealth of input specifications ALE does. Some of ALE's features that are not included in AMALIA include lexical rules, free use of definite clause attachments and disjunctive descriptions. On the other hand, development of grammars in AMALIA is made easier due to the GUI and its improved performance over ALE. A complete description of AMALIA's implementation, its deviations from ALE's input language and a complete users' guide, is given in Wintner, Gabrilovich, and Francez (1997).
To compare AMALIA with ALE we have used a few benchmark grammars. Both systems were used to compile the same grammar and to parse the same strings. We shortly describe below each of the grammars, and summarize the results of a performance comparison of AMALIA and ALE in figure 3.24. All times are in seconds; in ALE we measured the time for the first result to be displayed, and in AMALIA -the time for all the results.
The first grammar is an early version of the HPSG-based Hebrew grammar described in the next chapter. It consists of 4 rules and one empty category; the type hierarchy contains 84 types and 32 features, and the lexicon contains 13 words. The second grammar is an HPSGbased grammar for a subset (emphasizing relative clauses) of the Russian language, developed by Evgeniy Gabrilovich and Arkady Estrin. It consists of 8 rules and 76 lexical entries; the type hierarchy contains 151 types and 31 features. The third example is a simple grammar generating the language {a n b n | n > 0}. While the execution times for this simple grammar are less important, the differences in compilation time indicate a major advantage in using AMALIA for instructional purposes; in such cases grammars are compiled over and over again, while they are usually executed only a few times.  ID schemata only license certain phrase combinations. They do not specify all the constraints imposed on the involved sub-phrases, as these are articulated by the principles. However, in a system that is based on phrase-structure rules (e.g., ALE) the principles and the schemata must be interleaved: each rule encodes not only the phrase structure, but also constraints imposed by the grammar principles.
Consider, for example, the head-subject schema of HPSG, which states that a phrase with an empty subj list can be constructed by combining a (head) phrase, whose subj list is of length 1, with a (subject) phrase. Nothing in the schema relates the subject to the head; it is the subcategorization principle that requires that the subject be unifiable with the single element in the head's subj list. Furthermore, the head feature principle requires that the values of the head features in both the phrase itself and its head sub-phrase be identical. The first rule listed below (figure 4.1) combines these constraints: it states that a phrase can be constructed out of two sub-phrases, the subject and the head, where the first element (the value of the hd feature) in the subj list of the head is token-identical to the subject (through the use of the Subj variable), and the head features of the phrase and its head are token-identical (through the use of the Head variable).
Subject-Head schema Most importantly, this schema licenses the combination of a subject with a predicate to form a sentence. The properties of the subject are taken from the subj feature of the head daughter. The schema is listed in figure 4.1.
Head-Complement schema The rest of the complements, other than the subject, are combined with the head by the head-complement schema. Once again, the appropriate complements are determined by the head and are specified as the elements in the list comps, as shown in figure 4.2.
Head-Marker Schema Markers are used to guarantee that a certain modifier combines only once with a certain head. A typical example is quantifiers (such as 'every') modifying nouns. This schema is listed in figure 4.3.
Head-Adjunct schema Adjuncts can be combined with the heads they modify over and over again. In HPSG adjuncts select their heads -it is the adjunct that determines the features of the head it might be attached too, through the value of the feature mod , as depicted in figure 4.4.

The Structure of Noun Phrases in Hebrew
A noun phrase (NP) is a phrase that is headed by a noun 2 (N), optionally modified or complemented by various adjuncts. In this section we list the possible adjuncts and briefly discuss their character. A more thorough discussion of selected phenomena is provided in the next sections. More Hebrew data as well as further references can be found in (Ornan, 1964;Ornan, 1979;Glinert, 1989;Wintner, 1991;Yizhar, 1993). A noun is a word whose head feature has the type noun and whose cont feature is of type nom obj. The head feature of nouns carries an additional (boolean) feature, def, which is explained in section 4.3.3 below. Hebrew nouns are specified for gender, number and person 3 , and these three features are listed as part of the index feature of nouns. Figure 4.5 depicts the lexical entry of the common noun sepr (book), where ' ' represents an empty list and '{}' denote a set.   Definite article The definite article hais separated from the other determiners for reasons that are explicated in section 4.3.

Post-head adjuncts
Nominal complement Hebrew allows a very elaborate system of nominal-nominal compounds. The first nominal might be a noun or, rarely, an adjective; it is the syntactic head of the compound, and it is morphologically marked. The second nominal can be any NP. Compounds are discussed in section 4.4. Adjectives Hebrew adjectives are marked for number, gender and definiteness, on which they must agree with the head noun.
Prepositional phrases The rules that govern the combination of prepositional phrases to head nouns in Hebrew are very similar to those in English.
Subcategorized complements Certain nouns subcategorize for particular complements. For example, verbal nouns such as racon (wish) permit an infinitival verb phrase as a complement. This is encoded in the list of complements (the value of comp) in the lexical entries of the nouns.
Relative clauses Are not covered in our grammar.
As mentioned above, a thourough and complete description of the linguistic data is outside the scope of this work. The reader is referred to, e.g., (Ornan, 1964;Ornan, 1979;Glinert, 1989;Yizhar, 1993) for more details. (8) to kenurio to kokino podilato the new the red bike "the new red bike" (9) ta dio ta podilata ta kokina the two the bikes the red "the two red bikes" Kolliakou (1996) concludes that the Greek definite article is not a regular determiner, but constitutes a category of its own. It does not head the phrase it occurs in (as was suggested by (Netter, 1994) for Germanic languages); rather, it functions as an adjunct: it is optional, and it selects the head it modifies by specifying this head as the value of the MOD feature. Furthermore, the definite article marks the phrase it occurs in as definite. This is achieved by introducing a new feature of nominals, UNIQUE, 5 whose (boolean) value is '+' iff the nominal is definite. Naturally, the value of this feature in the lexical entries of nominals is '−' (since they are indefinite by default).

An Analysis of Hebrew Definites
The analysis of Kolliakou (1996) employs a non-quantificational approach to the semantics of definites. The UNIQUE feature is a semantic one (it is part of the CONTents of a phrase), and is the only indication of the definiteness of the phrase. This is in contrast to the approach of (Pollard and Sag, 1994) that is based on Cooper Storage of quantifiers. Whatever approach to semantics is taken, it is clear from examples (1) -(6) that agreement in definiteness among elements of the NP in Hebrew is a morpho-syntactic process, and we account here for this component of the grammar only.
In contrast to Greek, Hebrew exhibits no cases of monadic definites, so all we have to account for is the case of polydefinites. A major observation here is that the definite article attaches only to words. Therefore, it seems reasonable to account for definite article combination by means of a lexical rule that creates a definite nominal out of an indefinite one. For a detailed discussion of the definite article in Modern Hebrew, see (Ornan, 1964).
The Definite Lexical Rule (DLR) operates on various kinds of nominals: nouns (e.g., sepr), adjectives (e.g., gadol), ordinals (e.g., $eni), demonstratives (e.g., ze) and cardinals (e.g., $lo$a). In all categories its effect on the phonology is that of prefixing it with ha-. To emphasize the fact that definiteness agreement in Hebrew is not a semantic process, we add a boolean feature DEF to the CATegory of nominals (rather than to their CONTent). The DLR changes the value of the path SYNSEM|LOC|CAT|DEF from '−' to '+'. When the DLR operates on adjuncts, it additionally changes the value of the path MOD|LOC|CAT|DEF in the same manner. Thus it is guaranteed that definite adjectives, for example, are not only specified as definite but also select definite heads. The effect of the DLR when applied to a few nominals is exemplified in figure 4.6.
Once the process of adding the definite article is taking place in the lexicon, the head-adjunct schema can remain intact. Moreover, the agreement in definiteness between a nominal and its adjuncts is stated in the lexical entry of the adjuncts, just like agreement on number and gender is.
Cardinals introduce an irregularity to the analysis of definites. As mentioned above, cardinals can combine with the definite article in Hebrew. However, such constructs are used only in elliptic phrases. In full noun phrases, when the head noun is present, the definiteness agreement between    (10) to (14) below. (10) $lo$a sparim three books "three books" ?$lo$a ha-sparim three the books "?the three books" $lo$t ha-sparim three-'nismak' the books "the three books" ?$lo$t sparim three-'nismak' books "?three books" (14) * ha-$lo$a ha-sparim the three the books "?the three books" Notice that (14) is ungrammatical because the correct way of marking definiteness of cardinal in Hebrew is by using the 'nismak' form, and not because the phrase ha-$lo$a is ungrammatical. Indeed, this last phrase can be used in elliptical structures such as (15): (15) qaniti $lo$a sparim. koll ha-$lo$a b-'anglit I-bought three books. All the three in-English "I bought three books. All three of them are in English" The 'nismak' form of nominals is an inflection of their regular form, and therefore is obtained as the outcome of a lexical rule. As far as definiteness is concerned, when the DLR operates on an indefinite cardinal, its output is the 'nismak' form rather than the regular combination of haand the cardinal. All other details remain the same. The definite hais combined with cardinals by a different mechanism that is not discussed here.

Noun-Noun Constructs
Noun-noun compounds are constructed in a special way in Hebrew: the head noun, which appears first in the compound, has a marked morphological form 7 -'nismak'. Most NPs can serve as the adjunct of a compound. Syntactically, the compound inherits all the features of the 'nismak', with the exception of definiteness, which is inherited from the NP complement. Consider the following examples: (16) pirxei gann yapim flowers-pl-'nismak' garden-sg beautiful-pl "beautiful garden flowers" (17) pirxei ha-gann ha-yapim flowers-pl-'nismak' the garden-sg the beautiful-pl "the beautiful garden flowers" In both examples the entire phrase is in plural, as can be seen from the adjective, because the head noun pirxei is in plural. However, (17) is definite while (16) isn't, due to the definite article modifying the complement gann.
The process of compounding is recursive, as the resulting compound is a legitimate NP for combining with some other 'nismak' form. When more than two nouns are combined, the resulting phrase might be (if the nouns have the same gender and number) syntactically ambiguous: example (18) can be translated as "my fat aunt's cow" or as "my aunt's fat cow". The 'nismak' form is generated from the regular noun form by means of the 'nismak' lexical rule (NLR). Apart from modifying the phonology of the noun, this rule has a double effect. First, it adds a subcategorized NP complement to the COMP list of the noun, to express the expectation for an NP complement; second, it unifies the values of the DEF feature of the noun and its newly added complement. When the noun is complemented, the resulting phrase inherits the definiteness from the adjunct. Figure 4.7 depicts the effect of applying the NLR to the noun praxim (flowers).   Notice that the lexical entry of the 'nismak' noun pirxei, listed in figure 4.7, does not specify any value for the DEF feature. Hence, the DLR cannot be applied to pirxei, as it only applies for nominals that are specified as DEF −. This corresponds to the observation that 'nismak' nouns cannot be modified by the definite article in Hebrew. Once the 'nismak' lexical rule is applied to 'nismak'-form nouns, their lexical entry specifies that they subcategorize for a nominal complement. Noun-noun compounds can thus be constructed by the head-complement schema (figure 4.2).

Chapter 5 Conclusion
As linguistic formalisms become more rigorous, the necessity of well defined semantics for grammars increases. We presented an operational semantics for TFS-based formalisms, making use of an abstract machine specifically tailored for this kind of applications. In addition, we described a compiler for a general TFS-based language. The compiled code, in terms of abstract machine instructions, can be interpreted and executed on ordinary hardware.
We have formalized in this thesis the concepts of grammars and languages for linguistic formalisms that are based on typed feature structures, using the notion of multi-rooted structures that generalize feature structures. We use multi-rooted structures for representing grammar rules as well as (the equivalent of) sentential forms that are generated during parsing. We described a computational process that corresponds to parsing with respect to such formalisms. We thus achieved two different specifications, namely a declarative (derivation-based) one and an algebraic (computation-based) one, for the semantics of those formalisms. Next, we have proved that the two specifications coincide, namely that the computational process induced by the algebraic specification is correct with respect to the declarative specification. Finally, we formally characterized a subset of the grammars, off-line parsable ones, for which termination of parsing can be guaranteed. Making use of the well-foundedness of the subsumption relation, we proved that for every grammar in this class, parsing is finitely terminating.
This view of parsing with typed feature structures is the basis for the design of AMALIA, an abstract machine specifically tailored for executing code that is compiled from grammars. We detailed the architecture of the machine, its data structures and instruction set, along with the process of compilation of ALE grammars. The use of abstract machine techniques results in highly efficient processing. The system was implemented and a comparison to ALE shows a great improvement in both compilation and execution times.
The current implementation of AMALIA is not fully compatible with ALE. Several features of ALE are missing in our implementation, and therefore a natural extension of this project would be to add them. Most notably, AMALIA doesn't support the use of lexical rules, which are considered important for any reasonable grammar of natural languages. ALE also includes a component of definite clauses over TFSs which is missing in AMALIA -an interesting extension would be to link the abstract machine with a WAM-like machine that can handle definite clauses.
AMALIA's current compiler is relatively basic, and several optimizations might be introduced to it in the future. A major optimization might be achieved by incorporating static (compile-time) analysis of grammars. Several interesting questions, relating grammars to computer programs, arise: for example, what is the equivalent of dead-code elimination? How can concepts of structured programming be transferred to grammars? Can modules be defined for grammars, too?
A different line of improvements concerns the parsing algorithm incorporated by AMALIA. Currently only one, relatively simple, algorithm is inherent to the machine. An interesting extension would be to implement various algorithms, probably with user control over them, and to experiment their time and space efficiency.
AMALIA is currently being used as a platform for developing an HPSG grammar for the Hebrew language. While this endeavor is still underway, it serves as a realistic use of the system. The development of the grammar already resulted in many improvements and extensions to AMALIA, and the system proved stable and reliable enough to support it. We presented a partial HPSG-based grammar for a fragment of Hebrew, concentrating on noun phrases. We hope that this endeavor will serve as the basis for a more comprehensive, broad-coverage grammar of Hebrew.