Method of conjoining clauses during unification using opaque clauses

Abstract

A method of using a processor to conjoin a first clause and a second clause as part of a unification of a first graph. If the first clause is not associated with the first graph, then a third clause is created that is opaque and has a pointer to the first clause. Afterward, the third clause is conjoined with the second clause.

Claims

What is claimed is:

1. A method of using a processor in a natural language processing system to selectively conjoin a first clause and a second clause as part of a unification of a first graph data structure, the processor implementing the method by executing instructions stored in a memory, the method comprising the steps of:

a) determining if a first clause data structure representative of the first clause is included within the first graph data structure,

b) if the first clause data structure is not included within the first graph data structure, then

1) creating a third clause data structure, the third clause data structure having a pointer to the first clause data structure, the third clause data structure being opaque; and

2) if a second clause data structure representative of the second clause is included within the first graph data structure, conjoining the third clause data structure with the second clause data structure within the first graph data structure.

2. The method of claim 1 further comprising the steps of:

i) after step (b)(1), determining whether the second clause is opaque;

ii) if the second clause is opaque, determining whether the second clause and the first clause are both included within a same second graph data structure;

iii) if the second clause is opaque and the second clause and the first clause are both included within the same second graph data structure:

A) unwrapping the third clause data structure to obtain the first clause;

B) unwrapping the second clause data structure to obtain a fourth clause, the fourth clause not being opaque;

C) conjoining the first clause and the fourth clause to create a fifth clause, the fifth clause not being opaque;

D) creating a sixth clause data structure representative of a sixth clause in the first graph data structure, the sixth clause data structure being opaque and having a pointer to the fifth clause.

3. The method of claim 1 further comprising the step of:

c) after step (b), if the first clause data structure is included within the first graph data structure, then conjoining the first clause data structure with the second clause data structure in the first graph data structure.

4. The method of claim 2 further comprising the step of:

iv) after step (iii), if the second clause is opaque and the second clause and the first clause are not both included within the same second graph data structure, then conjoining the third clause data structure with the second clause data structure in the first graph data structure.

Description

REFERENCE TO MICROFICHE APPENDIX

This application includes a microfiche appendix for a computer program listing. This appendix includes 3 microfiche and 211 frames.

FIELD OF THE INVENTION

The present invention relates to natural language processing using computers. More particularly, the present invention relates to a method of conjoining clauses together during unification of feature structures to enable machine parsing of natural language in less than exponential time.

BACKGROUND OF THE INVENTION

The explosion of information has created an unfulfilled demand for automated processing of natural language documents. Such an ability would enable natural language interfaces to databases, automated generation of extracts and summaries of natural language texts, and automated translation and interpretation of natural language. Development of these technologies is hindered by the time required to process modern grammatical formalisms.

Many modern grammatical formalisms use recursive feature structures to describe the syntactic structure of natural language utterances. (See Appendix A for definitions of technical terms used herein.) For instance, Lexical-Functional Grammar (Kaplan and Bresnan 1982), Functional Unification Grammar (Kay 1979), HPSG (Pollard and Sag 1987) and Definite Clause Grammars (Pereira and Warren 1980) all use recursive feature structures as a major component of grammatical descriptions. Feature structures have the advantage of being easy to understand and easy to implement, given unification-based programming languages such as Prolog. However, they have the disadvantage of making the resulting grammatical formalisms difficult to parse efficiently, both in theory and in practice. In theory grammatical formalisms that use arbitrary recursive feature structures can be undecidable in the worst case (Blackburn and Spaan 1993). Even with suitable restrictions, such as the off-line parsability constraint of LFG, the formalisms can be exponential in the worst case (Barton, Berwick, and Ristad 1987). Although in practice the sorts of phenomena that make a formalism take exponential time are rare, untuned unification-based parsers commonly take minutes to parse a moderately complex sentence.

There have been a number of different approaches to making unification-based parsers run faster. One approach has been to focus on making unification itself faster. In addition to the general work on efficient unification (Knight 1989), there has been work within the computational linguistics community on undoable unification (Karttunen 1986), lazy copying (Godden 1990), and combinations thereof (Tomabechi 1991). Another approach has been to focus on the problem of disjunction, and to propose techniques that handle special cases of disjunction efficiently. For instance, disjuncts that are inconsistent with the non-disjunctive part can be eliminated early (Kasper 1987). Also, certain types of disjunctions can be efficiently processed by being embedded within the feature structure (Karttunen 1984; Bear 1988; Maxwell and Kaplan 1989; Dorre and Eisele 1990). There has also been some work on the context-free component of grammatical formalisms. It has been shown that the granularity of phrase structure rules has an important effect on parsing efficiency (Nagata 1992). Also, the strategies used for handling the interaction between the phrasal and functional components can make a surprising difference (Maxwell and Kaplan 1993).

Lazy copy links are another way of reducing the processing time associated with unification. They do so by reducing the amount of copying required by a unification-based chart parser (Godden 90). Whenever feature structures from daughter constituents get unified together, the feature structures must be copied to prevent cross-talk. This is because the daughter feature structures may be used in other analyses of the sentence. However, copying feature structures is very expensive. Thus, in 1990 Godden proposed lazy copying of feature structures. With lazy copying at first just the top levels of each feature structure are copied. At the fringe of what has been copied, standard lazy copy links point back to the material that hasn't been copied yet.

Contexted unification is another method of reducing the processing time required for unification. Contexted unification is a method for merging alternative feature structures together by annotating the various alternatives with propositional variables that indicate the alternatives that they came from. Contexted unification is based on ideas from Assumption-Based Truth Maintenance Systems (deKleer 1986). The following rules formalize the basic idea of contexted unification:

1. .phi..sub.1 .phi..sub.2 is satisfiable if and only if (p.fwdarw..phi..sub.1) (p.fwdarw..phi..sub.2) is satisfiable, where p is a new propositional variable;

2. If .phi..sub.1 .phi..sub.2 .fwdarw..phi..sub.3 is a rule of deduction, then (P.fwdarw..phi..sub.1)(Q.fwdarw..phi..sub.2).fwdarw.(PQ.fwdarw..phi..sub.3 ) is a contexted version of that rule, where P and Q are boolean combinations of propositional variables;

3. If P.fwdarw.FALSE, then assert P. (In ATMS terminology P is called a nogood.)

If we think of unification as a technique for making term rewriting more efficient by indexing equality relations in a feature tree, then contexted unification can be thought of in the same way, where the propositional variables get indexed with the equality relations, and then unification is performed in light of the above rules. Contexted unification is performed in three stages. First, the disjunctions are converted to conjunctions using Rule 1 above and instantiated as a feature structure. Afterward, feature structures are unified and nogoods are produced. Finally, the nogoods are collected and solved to determine which combinations of propositional variables are valid. This process was described in detail by Maxwell and Kaplan in 1989.

FIG. 1 illustrates a simple example of how contexted unification works. The first feature structure 20 results from instantiating the constraints (›A+!›B-!)(›C+!›C-!). The second feature structure 22 results from instantiating the constraints (›A+!›A-!)(›D+!›D-!). Propositional variables p, q, r, and s have been introduced to represent the four disjunctions in the two constraints. Unification of feature structures 20 and 22 yields feature structure 24 and the nogood (pr). To find solutions to feature structure 24, all possible combinations of the propositional variable are computed that are consistent with the known nogood. In this case there are twelve possible solutions: ##EQU1##

The main advantage of contexted unification is the postponement of taking the cross product of alternatives until the nogoods have been found. This is helpful for at least two reasons. First, taking the cross-product of propositional variables is computationally cheaper than taking the cross product of feature structures. Second, contexted unification prevents taking unnecessary cross products because they are not taken until after it is discovered whether the unification is valid. Cross products are not taken if the unification is invalid.

Despite all these different approaches to reducing the processing time required for unification, a need still exists to decrease the total time required to unify feature structures.

SUMMARY OF THE INVENTION

An object of the present invention is to reduce the time required to unify two feature structures by reducing the time required to copy attributes and values from those feature structures.

A method of using a processor to conjoin a first clause and a second clause together during unification of a first graph data structure with another graph data structure will be described in detail. First, the processor determines whether the first clause is associated with the first graph data structure. If not, then the processor creates a third clause that is opaque and has a pointer to the first clause. Afterward, the processor conjoins the third clause is with the second clause.

Other objects, features, and advantages of the present invention will be apparent from the accompanying drawings and detailed description that follows.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention is illustrated by way of example and not by way of limitation in the figures of the accompanying drawings. In the accompanying drawings similar references indicate similar elements.

FIG. 1 is an example of contexted unification.

FIG. 2 illustrates a computer system that utilizes the methods of the present invention.

FIGS. 3-6 illustrates an example of contexted unification according to the method of the present invention.

FIG. 7 is an object diagram of the software routines implementing the method of the present invention.

FIG. 8 is a flow diagram of the Main routine.

FIG. 9 is a flow diagram of the Process Edge Constraints routine.

FIG. 10 is a flow diagram of the Copy AV Pair routine.

FIG. 11 is a flow diagram of the Expand Lazy Links routine.

FIG. 12 is a flow diagram of the Copy Facts routine.

FIG. 13 is a flow diagram of the Conjoin Clauses routine.

FIG. 14 is a flow diagram of the Import Clause routine.

FIG. 15 is a flow diagram of the Get Edge Solutions routine.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

I. Overview

FIG. 2 illustrates computer system 30, which incorporates the contexted lazy copying methods of the present invention. Instructions 60 alter the performance of computer system 30, enabling system 30 to unify context free data structures in cubic time. Briefly described, instructions 60 reduce unification processing time by reducing the amount of information copied while unifying a first feature with a second feature structure. According to the method, alternative values of an attribute are represented by contexted lazy copy links, which indicate the analysis with which they are associated. When used in conjunction with contexted unification and opaque contexts, the present method enables unification to occur in cubic time for the parts of the grammar that are context-free equivalent.

A. Computer System for Contexted Unification Using Contexted Lazy Copying

Prior to a more detailed discussion of the present invention, consider computer system 30. Computer system 30 includes monitor 32 for visually displaying information to a computer user. Computer system 30 also outputs information to the computer user via printer. Computer system 30 provides the computer user multiple avenues to input data. Keyboard 34 allows the computer user to input data manually, as does mouse 35. The computer user may also input information by writing on electronic tablet 36 with pen 38. Alternately, the computer use can input data stored on machine readable media 40, such as a floppy disk, by inserting disk into floppy disk drive 42. Optical character recognition unit (OCR unit) 44 permits users to input hard copy natural language document 46, which it converts into a coded electronic representation, typically American National Standard Code for Information Interchange (ASCII).

Processor 48 controls and coordinates the operation of computer system 30 to execute the commands of the computer user. Processor 48 determines and takes the appropriate action in response to each command by executing instructions stored electronically in memory, either memory 50 or on floppy disk 40 within disk drive 42. Typically, operating instructions for processor 48 are stored in solid state memory, allowing frequent and rapid access to the instructions. Memory 50 also includes cache memory for storing clauses and restriction solutions. Semiconductor memory devices that can be used to realize memory 50 include read only memories (ROM), random access memories (RAM), dynamic random access memories (DRAM), programmable read only memories (PROM), erasable programmable read only memories (EPROM), and electrically erasable programmable read only memories (EEPROM), such as flash memories.

II. The Problem with Standard Approaches to Unification

The contexted lazy copying method of the present invention takes advantage of the observation that standard approaches to parsing unification based grammars take exponential time even when the linguistic phenomena being modeled are context-free in power. That is to say, even when linguistic phenomena can be represented using simple phrase structure rules, such that a phrase structure parser will take at most O(n.sup.3) time to parse a sentence, where n is the length of the sentence in words, a standard unification based feature structure parser modeling the same sentence will take O(2.sup.n) time. Understanding why adding feature structures so dramatically increases parsing time requires an understanding of how a context-free grammar can be parsed in cubic time using a chart, and why adding feature structures makes the resulting system exponential if the standard approaches are used. Both topics are discussed in detail below.

A. Parsing Using a Chart

A chart is simply a data structure for caching the constituents that have already been constructed by a parser. The main advantage of having a chart is that the parser can reuse existing constituents as it tries to parse the sentence in different ways (Sheil 1976). If the grammar is context-free, then the parser doesn't need to know how constituents get constructed, only that they are constructable. For instance, the parser will need to know whether there is an NP that goes from the fifth word to the tenth word, but it doesn't need to know whether the NP has a PP in it. Because of this, there are only O(Cn.sup.2) different constituents that might be constructed for a sentence of length n, where C is the number of different categories that the grammar allows. The n.sup.2 comes from the cross-product of all possible word positions. Conceptually, the chart is just a three-dimensional array of (Category, Left Position, Right Position) that indicates whether or not there is a constituent of type Category that starts at the Left Position and ends at the Right Position. A sentence has a parse if there is an S category that begins at the beginning of the sentence and ends at the end of the sentence. One way to fill in the chart is to start with all one word constituents, then build all of the two word constituents, then the three word constituents, and so on with each level building on the results of the previous levels. This is called the CKY algorithm (Younger 1967). The reason that the algorithm is On.sup.3 rather than On.sup.2 is that each constituent can be built in multiple ways. In the worst case, a constituent that is On in size can be built in On different ways. To build On.sup.2 constituents in On ways each requires On.sup.3 time. The CKY algorithm requires that constituents be built in a particular order, from smaller to larger. A more flexible way of building a chart is to keep an agenda of constituents that haven't been processed (Kaplan 1973, 1975). The constituents are taken off of the agenda one at a time, and processed as follows. Each constituent looks to its left and its right for constituents that it can combine with. When it finds a constituent to combine with, it checks the chart to see if the resulting constituent is already in the chart. If it isn't, then the constituent is added to the chart and placed on the agenda. The process then continues until the agenda is empty. The agenda makes things more flexible because constituents can be taken off of the agenda in any order. This sort of parser is called an "active chart parser".

As described, the above algorithms only determine whether or not a sentence is parsable, they do not determine what the valid parse trees are. However, this information can be obtained by simple additions to these algorithms. Whenever a constituent is constructed out of sub-constituents, the construction is recorded as a local subtree on the constituent that was constructed. A chart annotated with such subtrees is called a "parse forest" . When the parser is done, a particular parse tree can be read out by starting at the S constituent that spans the whole sentence, and picking one subtree at random. Then for each daughter constituent, one subtree is picked at random. This process is carried on until the tree is fully specified. In general, there can be exponentially many such fully-specified trees, but the parse forest for them can be produced in cubic time because they are stored in a compact representation.

B. The Effect on Parsing of Adding Feature Structures

Many grammar formalisms add feature structures to a backbone of context-free phrase structure rules. Depending upon the grammar the context-free rules may be explicit, as is the case Lexical-Functional Grammar (Kaplan and Bresnan 1982), or implicit as the case with Functional Unification Grammar (Kay 1979).

A standard approach to parsing feature structures, regardless of whether the context-free rules are explicit or implicit, is to first build a context-free phrase structure chart, and then to make a second pass on the chart data structure, building feature structures bottom-up (see Maxwell and Kaplan 1993). First, feature structures are instantiated from lexical items according to the feature constraints given. If the lexical items are ambiguous in any way, this will produce multiple feature structures. Then, feature structures for a mother constituent are constructed by taking the cross-product of the feature structures that belong to the daughter constituents. We take the cross-product in order to filter out any combinations that may be inconsistent. The result is a set of feature structures that are consistent to this point. If there is more than one way of constructing the mother constituent out of daughter constituents, then the sets of feature structures produced from all of the analyses is unioned together. This process continues bottom-up until feature structures for all of the constituents have been constructed.

This process is exponential in the worst case because of the cross-product that occurs at each level. For instance, if each lexical item is two ways ambiguous, then even if the phrase structure grammar is unambiguous there can be O(2.sup.n) different feature structures for the top constituent. If only finite-valued features are used, then a parser can be made to run in cubic time. This is because there is only a finite number of feature structures possible, and at each level we only have to keep track of which of these is possible without enumerating all of the ways that we got them. Once we reach the upper bound on the number of possible feature structures then the number of feature structures at each level stops growing. If all of the feature values are binary, then the top level constituent can have at most O(2.sup.k) different feature structures, where k is the number of different features. Thus, we can turn an exponential in sentence length into an exponential grammar constant by using only finite feature graphs. Unfortunately, the time required to parse non-finite feature structures can not be reduced in the same manner.

III. Contexted Lazy Copying

The methods described herein reduce the time required to unify feature structures during parsing and generation by introducing contexted lazy copy links. This new type of lazy copy link allows multiple alternative values to be represented by multiple contexted lazy copy links, each of which has been annotated with the contexts in which it is valid. The data represented by these contexted lazy copy links is not copied into a graph data structure until it becomes relevant and is expanded gradually to ensure that only necessary information is copied. When used in conjunction with contexted unification and opaque contexts, contexted lazy copy links reduce the time required to unify feature structures. Accordingly, the present method is described in detail with respect to FIGS. 11 and 12 and as part of a method of unifying context free feature structures in cubic time.

A. Example of Contexted Unification with Lazy Context Copying An example of contexted unification with lazy contexted copying will aid the coming detailed discussion of instructions 60 for performing contexted unification with contexted lazy copy links. Accordingly, consider FIG. 3, which illustrates edge 70 and its two daughter edges 72 and 82. Daughter 72 begins with an empty graph 74 with contexted lazy copy links, indicated via dotted lines, pointing to alternative fully specified graphs 75, 76, 78, and 80. Note that each lazy copy link is annotated with a context, p:1, p:2, p:3, and p:4, each of which represents a mutually exclusive choice. The situation of daughter 82 is analogous to that of daughter 72.

Unification of graphs 74 and 84 begins with creation of empty graph 71 and assertion of contexted lazy copy links from graph 71 to graphs 74 and 84. These contexted lazy copy links are bolded to indicate that interaction between the lazy copy links has been detected and that graph 71 will have to be expanded, which, in turn, requires expansion of daughter graphs 74 and 84.

FIG. 4 illustrates graphs 71, 74 and 84 after the required expansion. Daughter graph 84 has been expanded by copying up the first level of the alternative graphs 86, 88, 90, and 92. As a result, graph 84 is no longer empty, now containing the attributes A, C, and D. The values for these attributes are indicated via multiple contexted lazy copy links which point to values within feature structures 86, 88, 90, and 92. Note that while attribute C takes values only in contexts q:1 and q:2 and attribute D takes values only in contexts q:3 and q:4, a single graph 84 can be created that represents all of these mutually exclusive alternatives. Daughter graph 74 is expanded in a similar fashion. Next, graph 71 is expanded by copying into it the first level attributes of graphs 74 and 84, A, B, C, and D, with contexted lazy copy links pointing to the alternative values for those attributes. Bolding of the contexted lazy copy links associated with the A attribute indicate that they are interacting. Thus, the A attribute of graph 71 must be expanded, which means the A attributes of graphs 74 and 84 must also be expanded.

FIG. 5 illustrates graphs 71, 74, and 84 after the expansion of their A attributes. With respect to graph 74, this expansion replaces the contexted lazy copy links with two context value pairs. The A attribute takes the value + when either context p:1, p:2, or p:3 is TRUE. On the other hand, the A attribute takes the value--when context p4 is TRUE. In contrast to graph 74, expansion of the A attribute in graph 84 results in a single uncontexted value because the A attribute takes the same value in all of the contexts associated with feature structure 84. Unification of the A attributes from graphs 74 and 84 results in two context value pairs for the A attribute of graph 71. One context value pair states that A=+ in all contexts while the other context value pair states that A=- in context p:4. These two context value pairs result in the nogood p:4 because attribute A cannot simultaneously take the values + and-.

After performing all unifications, the nogood database is used to determine the possible solutions to the chart. Naively combining the nogoods can result in exponential processing time to find the solutions for the chart. Further, if propositional variables are copied up from daughters to their mothers those propositional variable may encode the structure of the tree, violating context-freeness and requiring exponential processing time. To avoid these problems, new, opaque propositional variables are introduced at each level. These propositional variables are called "opaque" because their internal structure is not available to the higher level to which they are imported. The process of making a propositional variable opaque prior to its importation is called wrapping. The nogood database is then solved locally in terms of the opaque variables that are imported from below. If the grammar is context-free equivalent, then the number of opaque variables will be bounded, allowing the nogood database to be solved locally in terms of the opaque variables that are imported from below.

In general, each daughter constituent has a set of opaque variables that have been imported by the subtree used to construct a mother constituent. Solutions that assign the values of TRUE or FALSE can be found for these opaque variables using the nogood database. These solutions are found by taking the cross-product of the daughter solutions, which are then filtered by the local nogoods. If there are multiple subtrees, then the context of the local subtree is added to each solution. For each solution, the opaque variables of the mother constituent are evaluated to determine whether the local subtree solution makes the opaque variables TRUE or FALSE. Each such assignment becomes a solution to the mother's opaque variables. There may be several local solutions for each assignment of values to the mother's opaque variables. This is analogous to there being multiple subtrees for each constituent in a context-free parse forest, where the "constituent" in this case is some set of feature-value combinations.

FIG. 6 illustrates solution of the chart discussed in FIGS. 3-5. Daughter feature structure 74 has two opaque variables: O1 and O2. In contrast, daughter feature structure 84 has no opaque variables because none of its contexts are exported. This situation produces two external solutions for daughter 72: O1O2 and O2O1. The O1O2 solution represents three internal solutions: p1, p2, and p3. The O2O1 solution represents only the internal solution p:4. Daughter feature structure 84 generates just one external solution in the TRUE context, which represents four internal solutions. Solutions for mother edge 70 are constructed by taking the cross-product of the external solutions imported from daughter edges 72 and 82 and filtering those solutions by the local nogood O2. This produces one internal solution, O1O2, for edge 70, which is associated with the external solution TRUE. The internal solutions of each mother are used to track the daughter solutions that they came from to facilitate enumeration of solutions.

B. Overview of Data Structures and Instructions for Lazy Contexted Unification

FIG. 7 illustrates schematically instructions 60 for lazy contexted unification of feature structures while parsing or generating a language string. Instructions 60 may be stored in machine readable form in solid state memory 50 or on floppy disk 42 placed within floppy disk drive 40. Instructions 60 may be realized in any computer language, including Prolog, LISP and C++.

Instructions 60 are organized as a hierarchical set of subroutines 100, 102, 104, 105, 108, 110, 112, 114, and 116. Main 100 controls the parsing of the string by calling Process Edge Constraints 102 and Get Edge Solutions 104. Process Edge Constraints 102 takes the constraints imposed on each edge and generates edge data structures for each edge. In doing so, subroutine 106 calls upon Copy AV Pairs 106. Subroutine 106 handles the copying of attribute value pairs from one graph to another by calling upon subroutines 108 and 110. Expand Lazy Links 108 expands a contexted lazy copy link by copying up one level of attributes and adding a new contexted lazy copy link for each attribute copied. Copy Facts 110 copies attributes from one graph into another. In doing so, subroutine 110 calls Conjoin Clauses 112. Conjoin Clauses 112 conjoins two contexts, or clauses, together to produce a new clause, which may be opaque, when appropriate. Import Clause 116 generates opaque clauses when a clause is being imported into a graph. Finally, Get Edge Solutions 104 takes the feature structures generated by subroutine 102 and determines possible solutions to the root spanning edge.

The upcoming detailed discussion of instructions 60 is aided by knowledge of the data structures used, which are stored in memory 50. Instructions 60 use four classes of data structures: chart, graph, clause, and solution data structures. Chart Data structures include Edge Data Structures and Subtree Data Structures. Each Edge Data Structure represents an edge and includes the following information:

    ______________________________________
    Edge›
    id: an integer uniquely identifying this edge
    right: an integer identifying the rightmost word of the edge
    left: an integer identifying the leftmost word of the edge
    category: indicates the grammatical category of the edge; e.g., NP, S,
    VP, etc.
    subtrees: a list of the various ways of making this edge
    graph: a pointer to the graph data structure for this edge
    Each Subtree Data Structure represents a subtree in Chomsky Normal
    Form. and includes the following information:
    Subtree›
    partial: points to the left daughter of the rule, a partial starts at
    the
    leftmost word of the edge and ends somewhere in the middle
    complete: points to the right daughter of the rule, a complete starts
    somewhere in the middle of the edge and ends at the rightmost word of
    the edge
    constraint: defines how partial and complete should be combined to
    produce the subtree
    graph: a pointer to the graph data structure for this subtree
    !
    ______________________________________

    ______________________________________
    Graph ›
    attrs: a list of pointers to the AVPairs associated with this graph data
    structure
    context: represents the context that this graph is in, and corresponds a
    variable assigned to a subtree to distinguish it from other valid
    subtrees
    associated with the same edge
    nogood: a boolean value indicating whether this feature data structure
    is
    nogood
    nogoods: a list of clauses that are nogood and associated with this
    graph
    edge: a pointer to the edge associated with this graph
    disjunctive: a boolean value that indicates whether or not the graph is
    an OR graph; i.e., a single graph that represents many alternative
    graphs
    clauses: a list of clauses allocated in this graph
    disjunctions: a list of locally instantiated disjunctions
    solutions: a list of pointers to Restriction Sets and their solutions
    ______________________________________

    ______________________________________
    AVPair›
    attr: the name of the type of attribute
    attrs: a list of pointers to the attributes that are included in the
    feature
    structure that this AVPair represents
    equals: a list of pointers to CVPair data structures that store the
    value
    for this attribute; e.g., if attr is NUM then the values in this field
    might by
    SG in one context and PL in another context
    copies: a list of pointers to CVPair data structures that store copy
    links
    to values that have been copied to or copied from this AVPair
    contexts: contexts in which this AVPair already has constraints
    prefix: a pointer to the AVPair that includes this AVPair. For example,
    in
    the LFG term (.uparw. SUBJ NUM), the NUM AVPair would have the
    (.uparw.SUBJ) AVPair as its prefix.
    graph: a pointer to the feature data structure that this AVPair belongs
    to
    expanded: a boolean value that indicates whether the contexted lazy
    links associated with this AVPair have been expanded
    ______________________________________

    ______________________________________
    CVPair›
    contexts: the context, or clause, associated with this value, for
    regular
    copy links the context is TRUE, any other value indicates a contexted
    value
    value: this field my include a value or a pointer to another AVPair data
    structure, depending on whether the pointer to this CVPair is stored in
    the equals field or copies field of an AVPair
    lazy: a boolean variable that indicates whether the value field is a
    forward copy link pointing forward to a recipient or is a lazy copy link
    that
    points backward to a source
    ______________________________________

    ______________________________________
    Clause:›
    type: Clause type- AND, OR, CHOICE, OPAQUE, nogood, TRUE
    body: union of{
    - this type of clause is a conjunction of contexts
    first: a pointer to the first clause of the conjunction
    rest: a pointer to the rest of the conjoined clauses
    OR{--this type of clause is a disjunction of contexts--
    first: a pointer to the first clause of the disjunction
    rest: a pointer to the rest of the disjoined clauses
    }
    NOT{--this type of clause is a negation of a context--
    negated: the clause negated
    }
    - this a primitive choice of disjunction
    disjunction: pointer to disjunction data structure
    containing the choice
    }
    OPAQUE{--this imports a context
    imported: the imported clause that is being wrapped
    graph: a pointer to graph data structure from which clause was imported
    }
    }
    graph - a pointer to the graph data structure with which this clause is
    associated
    cache - a pointer to an area of the clause cache associated with this
    clause. This area of the clause cache stores results of previously
    performed
    operations with this clause
    exported - a boolean variable that indicates whether this clause has
    been imported to another graph data structure
    nogood - boolean variable that indicates whether this clause has been
    determined to be nogood
    !
    ______________________________________

    ______________________________________
    Disjunction›
    count - integer indication the number of disjuncts in this disjunction
    context - the context with which this disjunction is associated
    arm1 - the first choice context (if only one)
    disj1 - the first choice disjunction (if more than one)
    arm2 - the second choice context (if only one)
    disj2 - second choice disjunction (if more than one)
    ______________________________________

    ______________________________________
    Restriction Set ›
    restriction set: a list of clauses given to Get Edge Solutions for
    solution
    solutions: a list of pointers to restricted solution data structures
    for the restriction set
    ______________________________________

    ______________________________________
    Restricted Solution ›
    clauses: the group of clauses that make up a solution. For
    example, if the restriction set is a:1, b:0, and (a:0 & b:0), then a
    solution
    might b:0 and (a:0 & b:0). This should be a subset of the restriction
    set. If
    there is a clause in the restriction set that isn't in this field, then
    it's value
    is presumed to be FALSE.
    map: list of pointers to Internal Solution data structures that
    evaluate to the solutions in the clauses field. For any particular
    restriction
    set, all of the internal solutions must be a member of the map of
    exactly
    one restricted solution. Each internal solution appears once in each
    restriction set.
    ______________________________________

    ______________________________________
    Internal Solution ›
    graph - a pointer to the graph that this internal solution was
    extracted from
    choices - a list of local choices of local disjunctions
    partial - a solution for the partial edge; i.e., left daughter
    complete - a solution for the complete edge
    ______________________________________

• Inventors
  Maxwell, III, John T.; Kaplan, Ronald M.;
• Assignee
  Xerox Corporation (Stamford, CT)
• Published
  May-11-1999
• Current US Classes:
  704/10
  704/9
  717/143
• Application #
  672515
• International Classes
  G06F 17//20
• Field of Search
  704/2 704/7 704/9 704/4 704/5 704/100 704/102
• Examiner
  Hudspeth; David R.
• US Patent References:
  5819210