US6064953A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for creating a disjunctive edge graph from subtrees during unification
Assignee: Xerox Corp
•
Filing: 1998-06-18
•
Granted: 2000-05-16
•
Expires: 2018-06-18
Abstract
Abstract A method of unifying edge data structures using a processor. The method begins with creation of a first edge data structure and unifying it with a second edge data structure. If during unification any of the contexted lazy copy links associated with the second graph data structure are activated, then second graph data structure is expanded. Expansion involves first selecting a contexted lazy copy link from among the contexted lazy copy links associated with the second graph data, selecting a selected attribute from the subtree feature structure pointed to by the selected contexted lazy copy link, making a copy of the selected attribute and storing the copy of the selected attribute in the second graph data structure as a second attribute, and adding a contexted lazy copy link from the second attribute to the selected attribute value.
Inventors
- 👤 John T. Maxwell, III
- 👤 Ronald M. Kaplan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-10 01:23
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/30; G06F8/31; G06F8/313; G06F8/3135; G06F40/00; G06F40/20; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99936; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
133 words
A method for constructing a graph for an edge from a plurality of graphs associated with a corresponding plurality of subtrees in a natural language processing system, the method comprising the steps of: creating a first graph for the edge, wherein the first graph is empty upon creation; creating a disjunct within the first graph by producing a plurality of contexted variables representative of the plurality of graphs associated with the corresponding plurality of subtrees, wherein the disjunct has a number of disjunctions equal to the number of subtrees; associating a selected subtree graph, chosen from the plurality of graphs associated with the corresponding plurality of subtrees, with a first available disjunction in the first graph; and incorporating information derived from the selected subtree graph into the associated disjunction of the first graph.
Claim 2
Independent Claim
133 words
A method for constructing a graph for an edge from a plurality of graphs associated with a corresponding plurality of subtrees in a natural language processing system, the method comprising the steps of: creating a first graph for the edge, wherein the first graph is empty upon creation; creating a disjunct within the first graph by producing a plurality of contexted variables representative of the plurality of graphs associated with the corresponding plurality of subtrees, wherein the disjunct has a number of disjunctions equal to the number of subtrees; associating a selected subtree graph, chosen from the plurality of graphs associated with the corresponding plurality of subtrees, with a first available disjunction in the first graph; and incorporating information derived from the selected subtree graph into the associated disjunction of the first graph.
Claim 3
Dependent Claim
40 words
The method of claim 1, wherein the step of creating a first graph comprises the steps of: allocating a graph data structure representative of an edge graph; and marking the graph data structure as an "OR" type graph data structure.
Claim 4
Dependent Claim
24 words
The method of claim 1, further comprising the step of repeating the associating and incorporating steps for each subtree in the plurality of subtrees.
Claim 5
Dependent Claim
22 words
The method of claim 1, wherein the incorporating step comprises unifying the selected subtree graph with the first graph for the edge.
Claim 6
Dependent Claim
21 words
The method of claim 1, wherein each of the plurality of contexted variables corresponds to at least one opaque propositional variable.
Claim 7
Independent Claim
150 words
A method for using a processor to construct a graph for an edge from a plurality of graphs associated with a corresponding plurality of subtrees in a natural language processing system, the processor implementing the method by executing instructions stored in a memory, the method comprising the steps of: creating a first graph for the edge by producing a plurality of contexted variables representative of the plurality of graphs associated with the corresponding plurality of subtrees, wherein the first graph has a number of disjunctions equal to the number of subtrees; associating each graph in the plurality of graphs associated with the corresponding plurality of subtrees with a respective first available disjunction in the first graph; and unifying each graph in the plurality of graphs associated with the corresponding plurality of subtrees with the first graph by incorporating information from each graph in the plurality into its respective associated disjunction.
Claim 8
Independent Claim
150 words
A method for using a processor to construct a graph for an edge from a plurality of graphs associated with a corresponding plurality of subtrees in a natural language processing system, the processor implementing the method by executing instructions stored in a memory, the method comprising the steps of: creating a first graph for the edge by producing a plurality of contexted variables representative of the plurality of graphs associated with the corresponding plurality of subtrees, wherein the first graph has a number of disjunctions equal to the number of subtrees; associating each graph in the plurality of graphs associated with the corresponding plurality of subtrees with a respective first available disjunction in the first graph; and unifying each graph in the plurality of graphs associated with the corresponding plurality of subtrees with the first graph by incorporating information from each graph in the plurality into its respective associated disjunction.
References Cited (Backward Citations)
US5438511A
Cited
US5727222A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-05-16 | 2003-11-15 | 2004-05-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-16 | 2007-11-15 | 2008-05-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-16 | 2011-11-15 | 2012-05-16 | $7700.00 | Window Closed / Lapsed |