..._Xy^3.1

Technically, a variable may begin with an underscore, but such variables, said to be anonymous, have a very different status than those which begin with a capital letter. The use of anonymous variables is discussed later.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...e_list,^4.1

Set values, like those employed in HPSG, are not supported by ALE. In the categorial grammar in the appendix, they are represented by lists and treated by attached procedures for union and selection.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^4.2

In general, the amount of memory required to represent $n$ types is proportional to the number of pairs of consistent types. In the worst case, this is ${\cal O}(n^2)$ in the number of types.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^4.3

Using a typed version of the Martelli and Montanari (1982) algorithm, which was adapted to cyclic structures by Jaffar (1984), unification can be performed in what is known as quasi-linear time in the size of the input structures, where in this case, quasi-linear in $n$ is defined to be ${\cal O}(n \cdot \mbox{\it ack}^{-1}(n))$, where ${\it ack}^{-1}$ is the inverse of Ackermann's function, which will never exceed 4 or 5 for structures that can be represented on existing computers. There is also a factor in the complexity of unification stemming from the type hierarchy and appropriateness conditions, which we discuss below.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^4.4

The choice of totally well-typed structures was motivated by the desire to represent feature structures as records at run-time, without listing their features. Internally, a feature structure is represented as a term of the form Tag-Sort(V1,...,VN) where Tag represents the token identity of the structure using a Prolog variable, Sort is the type of structure, and V1 through VN are the values of the appropriate features, in alphabetical order of the features' names, which are themselves left implicit. Furthermore, the Tag is used for forwarding and dereferencing during unification.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^4.5

The only finite feature structures that could meet this type system would have to be cyclic, as noted in Carpenter (1992). The problem is that there is no most general such cyclic structure, so type inference cannot be unique.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^4.6

In theory (Carpenter 1992), this set is only required to be upward closed, which means that if $\sigma \in {\sf ExtType}$, and $\sigma$ subsumes $\tau$, then $\tau \in {\sf ExtType}$. This relaxation of our requirement that extensional types be maximal would actually not be too difficult to implement.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^4.7

This is given by the == operator in Prolog.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...ALE^4.8

The life-span of a feature structure in ALE is the period from its creation to the point when the user command currently being executed finishes, unless that feature structure is asserted as an edge in ALE's chart parser. In this case, the life of the feature structure ends when the edge is removed. Every new request for a parse to ALE removes all of the current edges.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^4.9

This is because the depth of dereferencing depends on the history of types a given structure is instantiated to. There is no path compression on-line, but it is carried out before an edge is asserted into the chart.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^4.10

Finding most general satisfiers for non-disjunctive descriptions, even those involving type inference, is quasi-linear in the size of the description. But it should be kept in mind that there is also a factor of complexity determined by the size of the type specification. In practice, this factor is proportional to how large the inferred structure is. In general, the size of the inferred structure is linear in the size of the description, with a constant for the type specification.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^4.11

It corresponds so closely with non-determinism that satisfiability of descriptions with disjunctions is $\mbox{\sc NP}$-complete. Furthermore, the algorithm employed by ALE may produce up to $2^n$ satisfiers for a description with $n$ disjunctions.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... rule^4.12

In the case of cats>, they are enforced after the list description itself is matched, and also after every element of the list is matched.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... structure-shared.^4.13

Recall that Prolog variables start with an upper-case letter.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... extensional.^4.14

An extensional type cannot be copied and has to be structure-shared if it occurs more than once in a feature structure. Extensional and intensional types are discussed in ALE  User's Guide.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... University^4.15

Sections T4.2.2-T4.2.4 ©2003, W. Detmar Meurers

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^4.16

This system was actually the precursor to ALE. It implemented a completely reversible constraint-based parser/generator with a weighting on the constraints based on their maximal non-determinism. Re-ordering constraints, however, proved to be insufficient for efficient parsing or generation, compared to a uni-directional system such as ALE.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^5.1

Thus, additional cuts might be necessary to ensure determinism, so that last call optimization is effective.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^5.2

As in Prolog, we refer to predicates by their name and arity.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^5.3

Table look-ups involved in unification in ALE rely on double hashing, once for the type of each structure being unified.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^6.1

Thus ALE's lexical rule system is not capable of handling cases of partial suppletion, where both a regular and irregular morphological form are both allowed. To allow two ouptut forms, one must be coded by hand with its own lexical entry or a separate lexical rule.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^6.2

By doubling the size of the BNF for rules, this requirement could be expressed.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^6.3

In a future release, cuts will be allowed within descriptions, to allow the user to eliminate disjunctive choice points when possible.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... University^7.1

©2003, Vanessa Metcalf and Detmar Meurers

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^A.1

Earlier versions of ALE also permitted incremental updating and retraction of empty categories. Because empty categories are now closed under phrase structure rules at compile-time, this is no longer possible.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...^B.1

Actually, this example is a bit of an improvisation -- the sample HPSG grammar included in the ALE distribution does not use inequations.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... structure^D.1

The reader is referred to the ALE User's Guide for the structure of this representation.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... University^E.1

©2003, W. Detmar Meurers

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.