...work
Research reported in this paper was supported in part by Contract MDA904-92-C-5189 from the U.S. Department of Defense.
...down,
CSP does not assume tree shaped search spaces. Neither do we, for that matter, although computational semantics generally present as tangled trees, a fact we take advantage of (see below).
...heuristics.
They can be used with heuristics as well, if desired.
...group.
This ``hunter-gatherer'' business is undoubtedly politically-incorrect. Be advised that we are in no way denigrating pre-industrialist cultures.
...variable.
If there is more than one, they can always be combined into one with ANDS: [A > 0 AND A < 10]
...constraints
Higher order constraints are also possible, but since they currently not used in Mikrokosmos, they will not be discussed here.
...constraints,
Meaning that the partial solution which assigns value X to variable A and Y to B satisfies the binary constraint 13#13.
...constraints.
The assignment of value X to variable A satisfies the unary constraint 15#15.
...variables.
In computational semantics, the maximum size of any domain is probably around 10 (10 word senses for a single lexical item). However, the average case domain size is less than 3. Thus, terms which involve domain size will be insignificant compared to the number of variables (actual words) in a problem, which can get to 40 or higher in long sentences. Later, time and space complexity terms involving the maximum number of constraints per variable will be used. A similar argument applies.
...arc
Note: the arcs must be identified before using this procedure. This can be accomplished by examining each constraint once. The algorithm above assumes separate arcs for both directions, i.e. AB and BA.
...{(A,2,),...}
That is, the assignment of value 0 to variable B supports the assignment of value 2 to variable A with respect to 29#29, along with any other supports.
...2.
That is, the assignment of the value 2 to A has two supports for the 32#32 constraint.
...O(n).
Note that [Tsang, 1993] as well as [Mohr and Henderson, 1986] give the complexity of step 3 as O(43#43e). They assume each arc can add a items to the FAIL-LIST, so that the WHILE loop can be executed ae times. It is easy to see, though, that this is excessive. A value can only be deleted once from its domain. The APPEND(FAIL-LIST,...) statements (lines 15 and 24) can be implemented so that duplicate variable-value pairs are not added, and the MEMBER(Y,DOMAIN(B)) statement (in line 23) prevents any variable-value pair that has been deleted from being re-added to FAIL-LIST. Thus, an is the correct limit for the WHILE loop.
...path
A path is a set of variables, each variable of which has an arc between itself and its adjacent variables.
...island'',
Discussion on ``islands'' follows below.
...constraints,
For example, Baltimore must come first because the supplies need to be picked up, then the cities where the perishable goods are sold must be next, etc.
...algorithm
Note that this is simplified; Freuder's algorithm will be described below.
...k
A solution of order k is an assignment of values to k variables; a solution set of order k is the set of all solutions of order k.
...variable.
Two solutions, each of order I-1, which differ in only one variable, will combine to give a solution of order I.
...(A,B,C,D).
Line 12a guarantees SOLUTION-A and SOLUTION-B differ by one variable. Line 13 performs the combination.
...Jacob-Smith
An imaginary company name, as well as a person's name.
...ontology,
See Section 4 for a discussion of ontologies and their place in computational semantics
...concepts
Concepts will be in CAPS. We use very simple concepts symbolized with English words, and simply list the constraints that would be specified in an ontology. We also assume an inheritance hierarchy (HUMAN IS-A ANIMATE), and a mechanism for identifying metonymy; for instance (ORG IS-A ANIMATE) because an ORG has MEMBERS that are HUMAN, and (ORG IS-A INANIMATE), because an ORG has a BUILDING that is an INANIMATE. Metonymy will be discussed in more depth below.
...involved:
Here, for clarity, we present each solution as a set of variable-value pairs, i.e 65#65 = {66#66}. After this, we generally will present only the values, with the assignment to variables obvious in context, i.e 67#67 = {(ORG)}.
...restricted.
SS-TSANG can also be built upon SS-FREUDER if (limited) propagation is desired.
...SS-1.
Because synthesizing order-3 solutions occurs only between order-2 solutions with 3 distinct variables (SS-1 line 12a), this will only occur between ``adjacent'' (as shown in Figure 7) order-2 solutions, as all other combinations would lead to 4 distinct variables. Likewise, higher order solutions only are synthesized from adjacent solutions of the next lower order.
...#essex#478>,
This ordering is arbitrary. The efficiency of SS-TSANG is greatly affected by the ordering chosen. This fact is recognized and expanded upon in our work.
...answer.
AKA The ``hit-your-head-against-the-wall phenomena''
...used.
For example, a potential path with a high estimated distance to goal can be excluded even though its total current distance is lower than the optimal path.
...variables,
Which is not detected by arc consistency until those variables are instantiated.
...one
Actually nonserial DP introduces methods for eliminating groups of variables - see below
...possible
Technically, there could be more possibilities, such as multiple In-Vertices combining with multiple lower-level subgraphs, but practically speaking, the Input-Complexity (see below) of these combinations is excessive)
...University,
Please see the CRL WWW home page for a more complete overview of the uK Project at http://crl.nmsu.edu/index.html
...style.
For example, see (Viegas and Nirenburg 1995) for a treatment of verbal ellipsis.
...verb:
An LFG-like syntactic description is used.
...used.
Except possibly in failure recovery situations, not discussed here.
...sentence
along with information added by other microtheories
...ontology.
The next section describes how the analyzer retrieves and applies constraints from the ontology
...event,
For example, a South-American Indian language has a single word for ``she carries water down to the river'', but our ontology sadly cannot map directly into such an event.
...languages.
For example, one word for a human drinking, another word for animals drinking.
...NMSU.
We would prefer to interleave semantics in the syntactic analysis process. Currently, we are investigating ways to modify the Pangloss-uK interface to provide a level of interleaving, especially with regards to PP attachments.
...meanings.
Again, this limitation will be removed shortly. Choosing between attachments will proceed in the same constraint-satisfaction paradigm as described for word senses, with some possible inputs from attachment microtheories such as ``minimal attachment'', etc..
...currently
It is clear that ORGANIZATION as AGENT or THEME should select different types of EVENTS than, say, HUMAN. As the uK ontology is refined, such knowledge will be added.
...HUMAN.
Please see the discussion of metonymy in the next section to understand how ORGANIZATION (grupo-roche's meaning) can meet a HUMAN constraint.
...``compania,''
The lexicon entries for ``a-traves-de'' needs to be consulted to determine these facts.
...EVENT)
Which asks ``Is ACQUIRE an EVENT?''
...constraints
The semantic constraints are drawn from the lexicon and ontology as described in the previous section.
...created.
But only at great expense.
...below:
The main point here is not why the scores given were assigned. See section 4 for a discussion of constraints and how scores are determined. These scores are only a fairly intuitive assignment of values that will be used to demonstrate the algorithms below.
...combined
Combining scores for a list of constraints is complicated. To simplify, we assume here that all individual constraint scores are multiplied together.
...reduced
By ``fully reduced'' we mean all child variables maximized with respect to a single parent, which cannot be reduced because it connects higher up in the tree.
...occur.
``Long distance'' dependencies do exist, but are relatively rare.
...plans
The total number of plans corresponds to the total number of words senses for all the words in the sentence.
...abstractions
Or macros, or subgraphs, or sub-groups, depending on your background.
...planner
A similar algorithm can be used for non-hierarchical inputs. PICARD does not require hierarchical semantic inputs.
...Spain.''
We emphasize that this is the best computationally, given the lexicon and semantic inputs in this simplified example.
...``non-dummy''
``Dummy'' plans are explained next.
...world:
As in Santa's.
...legally,
The object of N-Queens is to place N Queens on an N X N chessboard such that no Queen attacks any other Queen.
...constrained
Determining ``unconstrainedness'' is a peculiar, but potentially powerful outcome of constraint analysis.
...delayed
Unless all other decisions can be ruled out locally using the techniques described above.
...constraint-based
Elhadad uses functional unification to enforce constraint satisfaction. Although this certainly works, it has none of the efficiency advantages presented here.
...precondition
A constraint A is considered conflicting when the precondition requires that constraint A not be set. Also judged as conflicting is the plan that sets constraint A when the precondition requires constraint -A
...left
This can happen because there was only one plan to start with, or because the soundness procedure above eliminated one or more plans in a node, or the process being described here eliminated one or more plans in a node, or a combination of the last two processes left only one valid plan, or, finally, the solution synthesis mechanism chose one plan and ``failed'' all the others
...complete
Except for the non-monotonic plans and surface constraint types described below.
...critically
No other non-failed plans exist that could also satisfy its constraints.

Steve Beale
Wed Mar 26 09:27:50 MST 1997