Patent EP0365309A2 successfully refreshed from Google Patents.
← Back to Patent Explorer
EP0365309A2 Expired / Lapsed EP ⏱️ 0.0 years remaining

A data unification system and method

Assignee: Xerox Corp
•
Filing: 1989-10-18
•
Granted: —
•
Expires: 2009-10-18
📄 Original PDF 🌐 Google Patents 🔄 Sync Now

Abstract

Abstract Unification of a disjunctive system is performed based on context identifiers within data structures that correspond to disjunctions. Each context identifier is a logical combination of choices, with each choice identifying one of the disjuncts of a disjunction in the system. Each choice can include a disjunction identifier and a choice identifier identifying one of the disjuncts of the identified disjunction. The logical combination of choices in a context identifier thus corresponds to a combination of disjuncts, all of which could be from different disjunctions. If two data units have context identifiers identifying contexts that are genuine alternatives, those data units are not unified. Data units that have context identifiers that are not genuine alternatives are unified. A set of context-value pairs, referred to as a disjunctive value, can be unified with another disjunctive value by considering all combinations of pairs of context identifiers that include one context identifier from each disjunctive value. The number of combinations of context identifiers in each disjunctive value is reduced by combining context-value pairs: Pairs with equal value tokens are combined by merging their context identifiers and unifying the value tokens. Pairs with f-structures as values are combined by merging context identifiers and unifying the f-structures. An equality within a disjunct is handled by unifying the equated entities, but only in the context appropriate to that disjunct. If it is necessary to insert a pointer, the pointer is inserted so that it initially leads to a disjunctive value, with the source of the pointer indicating which of the context-value pairs in the disjunctive value is to be accessed. This technique can avoid exponential growth for some classes of the NP-complete problem that occur in such domains as natural language processing.

Inventors

  • 👤 John T. Maxwell Iii
  • 👤 Ronald M. Kaplan

Bibliographic Details

Application Number —
Jurisdiction EP
Data Source google_patents
Last Synchronized 2026-11-10 02:08
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/30; G06F8/31; G06F8/313; G06F8/3135

Claims Analysis

Total Claims: 12
Claim 1
Independent Claim 87 words
A system for unifying data, comprising: a data structure that includes a first data unit and a context identifier identifying a context; the context identifier and the first data unit being associated; and a processor for performing unification, the processor being adapted to access the first data unit in order to unify it with a second data unit, and to access the context identifier associated with the first data unit to use the context identifier to determine whether the first and second data units can be unified.
Claim 2
Independent Claim 87 words
A system for unifying data, comprising: a data structure that includes a first data unit and a context identifier identifying a context; the context identifier and the first data unit being associated; and a processor for performing unification, the processor being adapted to access the first data unit in order to unify it with a second data unit, and to access the context identifier associated with the first data unit to use the context identifier to determine whether the first and second data units can be unified.
Claim 3
Dependent Claim 15 words
The system of claim 1, in which the data structure includes the second data unit.
Claim 4
Dependent Claim 83 words
The system of claim 2, in which the data structure further includes a second context identifier in addition to the first above-mentioned context identifier, the second context identifier identifying a second context; the second data unit and the second context identifier being associated; the processor further accessing the second data unit in order to unify the first and second data units, the processor accessing the second context identifier and using it to determine whether the first and second data units can be unified.
Claim 5
Dependent Claim 75 words
The system of claim 3, in which the first and second contexts correspond respectively to first and second disjuncts of a disjunction within a disjunctive 'system, the first disjunct including a first value and the second disjunct including a second value different from the first value, the first data unit including a first value token corresponding to the first value and the second data unit including a second value token corresponding to the second value.
Claim 6
Dependent Claim 67 words
The system of claim 4, in which each of the first and second disjuncts includes a feature that can take the first and second values, the data structure further including a feature token corresponding to the feature; the processor further producing a third data unit as a result of unifying the first and second data units, the processor associating the third data unit with the feature token.
Claim 7
Independent Claim 32 words
The system of any preceding claim, in which the context identifier includes a first number identifying a set of genuine alternatives that includes the context, and a second number identifying the context.
Claim 8
Independent Claim 44 words
A method for unifying data, comprising: accessing a first data unit, a second data unit, and a context identifier associated with the first data unit, the context identifier identifying a context, and unifying the first and second data units based on the context identifier
Claim 9
Independent Claim 44 words
A method for unifying data, comprising: accessing a first data unit, a second data unit, and a context identifier associated with the first data unit, the context identifier identifying a context, and unifying the first and second data units based on the context identifier
Claim 10
Dependent Claim 38 words
The method of claim 7, further comprising accessing a second context identifier associated with the second data unit, the second context identifier identifying a context, the unifying step being based on both the first and second context identifiers.
Claim 11
Dependent Claim 60 words
The method of claim 8, in which the context identified by the first context identifier is a first context and the context identified by the second context identifier is a second context different from the first context, the unifying step further comprising determining whether the first and second contexts are genuine alternatives, based on the first and second context identifiers.
Claim 12
Dependent Claim 49 words
The method of claim 9, in which each of the first and second data units includes a respective value token corresponding to a value; the substep of unifying the first and second data units comprising determining whether they are consistent, based on whether their respective value tokens are consistent.

References Cited (Backward Citations)

No citation records indexed.

USPTO Annuity & Maintenance Windows

Maintenance schedule is calculated for granted US utility patents.

Assigned Categories & Tags

No categories assigned to this patent yet.

Assign Category Tag