US 5,438,511 A · Disjunctive unification

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. 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.

Claims51

Dependent claims

A system for solving a logical formula using unification, the logical formula including a plurality of terms;

at least one of the terms including a disjunction, each disjunction having a plurality of disjuncts, each disjunct having a respective context;
the system comprising:
a first data unit and a second data unit, the first data unit including data relating to a first one of the terms of the logical formula and the second data unit including data relating to a second one of the terms of the logical formula;
a first context identifier identifying a first context that includes the respective context of each of a first set of one or more disjuncts of the logical formula;
a second context identifier identifying a second context that includes the respective context of each of a second set of one or more disjuncts of the logical formula;
the first context applying to the first data unit and the second context applying to the second data unit;
and
a processor for performing unification, the processor including:
first means for accessing the first data unit and the second data unit and the first and second context identifiers;
and
second means for using the first and second context identifiers to determine whether to unify the first and second data units.

8 more elements

A method of solving a logical formula using unification, the logical formula including a plurality of terms;

at least one of the terms including a disjunction, each disjunction having a plurality of disjuncts, each disjunct having a respective context;
the method being performed with a system that includes:
a first data unit and a second data unit, the first data unit including data relating to a first one of the terms of the logical formula and the second data unit including data relating to a second one of the terms of the logical formula;
a first context identifier identifying a first context that includes the respective context of each of a first set of one or more disjuncts of the logical formula;
a second context identifier identifying a second context that includes the respective context of each of a second set of one or more disjuncts of the logical formula;
the first context applying to the first data unit and the second context applying to the second data unit;
and
a processor for accessing the first and second data units and the first and second context identifiers and for performing unification;
the method comprising steps of:
accessing the first data unit and the second data unit and the first and second context identifiers;
and
using the first and second context identifiers to determine whether to unify the first and second data units.

9 more elements

A computer-implemented method of solving a logical formula that contains linguistic information using unification, the logical formula including a plurality of terms that contain linguistic information;

at least one of the terms including a disjunction, each disjunction having a plurality of disjuncts, each disjunct having a respective context;
the method being performed with a computer system that includes:
memory;
a first data unit and a second data unit stored in the memory, the first data unit including data relating to linguistic information in a first one of the terms of the logical formula and the second data unit including data relating to linguistic information in a second one of the terms of the logical formula;
a first context identifier identifying a first context that includes the respective context of each of a first set of one or more disjuncts of the logical formula;
a second context identifier identifying a second context that includes the respective context of each of a second set of one or more disjuncts of the logical formula;
the first context applying to the first data unit and the second context applying to the second data unit;
the first and second context identifiers being stored in the memory;
unification instruction data stored in the memory;
the unification instruction data indicating first unification instructions and second unification instructions;
and
a processor connected for accessing the memory;
the processor executing the first unification instructions and the second unification instructions to perform unification of the first and second data units;
the method comprising:
operating the processor to access the unification instruction data and execute the first unification instructions;
the processor, in executing the first unification instructions, accessing the first data unit and the second data unit and the first and second context identifiers in the memory;
and
operating the processor to access the unification instruction data and execute the second unification instructions;
the processor, in executing the second unification instructions, using the first and second context identifiers to determine whether to unify the first and second data units.

16 more elements

A computer system for solving a logical formula that contains linguistic information using unification, the logical formula including a plurality of terms that contain linguistic information;

at least one of the terms including a disjunction, each disjunction having a plurality of disjuncts, each disjunct having a respective context;
the system comprising:
memory;
formula data stored in memory;
the formula data defining the logical formula;
unification instruction data stored in the memory;
the unification instruction data indicating first unification instructions and second unification instructions;
and
a processor connected for accessing the memory;
the processor accessing the formula data and the unification instruction data and executing the first unification instructions and the second unification instructions to perform unification;
the processor, in executing the first unification instructions, accessing the formula data in the memory and using the formula data to produce first and second data units and first and second context identifiers and storing the first and second data units and the first and second context identifiers in the memory;
the first data unit including the first context identifier and the second data unit including the second context identifier;
the first data unit including data relating to linguistic information in a first one of the terms of the logical formula and the second data unit including data relating to linguistic information in a second one of the terms of the logical formula;
the first context identifier identifying a first context that includes the respective context of each of a first set of one or more disjuncts of the logical formula;
the second context identifier identifying a second context that includes the respective context of each of a second set of one or more disjuncts of the logical formula;
the first context applying to the first data unit and the second context applying to the second data unit;
the processor, in executing the second unification instructions, accessing the first data unit and the second data unit and the first and second context identifiers in the memory and using the first and second context identifiers to determine whether to unify the first and second data units.

14 more elements

at least one of the terms including a disjunction, each disjunction having a plurality of disjuncts, each disjunct having a respective context;
the method being performed with a computer system that includes:
memory;
formula data stored in memory;
the formula data defining the logical formula;
unification instruction data stored in the memory;
the unification instruction data indicating first unification instructions and second unification instructions;
and
a processor connected for accessing the memory;
the processor accessing the formula data and the unification instruction data and executing the first unification instructions and the second unification instructions to perform unification;
the method comprising:
operating the processor to access the unification instruction data and execute the first unification instructions;
the processor, in executing the first unification instructions, accessing the formula data in the memory and using the formula data to produce first and second data units and first and second context identifiers and storing the first and second data units and the first and second context identifiers in the memory;
the first data unit including the first context identifier and the second data unit including the second context identifier;
the first data unit including data relating to linguistic information in a first one of the terms of the logical formula and the second data unit including data relating to linguistic information in a second one of the terms of the logical formula;
the first context identifier identifying a first context that includes the respective context of each of a first set of one or more disjuncts of the logical formula;
the second context identifier identifying a second context that includes the respective context of each of a second set of one or more disjuncts of the logical formula;
the first context applying to the first data unit and the second context applying to the second data unit;
operating the processor to access the unification instruction data and execute the second unification instructions;
the processor, in executing the second unification instructions, accessing the first data unit and the second data unit and the first and second context identifiers in the memory and using the first and second context identifiers to determine whether to unify the first and second data units.

17 more elements

A computer system for solving a logical formula that contains linguistic information using unification, the logical formula including a plurality of terms that contain linguistic information;

at least one of the terms including a disjunction, each disjunction having a plurality of disjuncts, each disjunct having a respective context;
the system comprising:
memory;
formula data stored in memory;
the formula data defining the logical formula;
unification instruction data stored in the memory;
the unification instruction data indicating first unification instructions, second unification instructions, third unification instructions, and fourth unification instructions;
and
a processor connected for accessing the memory;
the processor accessing the formula data and the unification instruction data and executing the first unification instructions, the second unification instructions, the third unification instructions, and the fourth unification instructions to solve the logical formula;
the processor, in executing the first unification instructions, accessing the formula data in the memory and using the formula data to produce first and second data units and first and second context identifiers and storing the first and second data units and the first and second context identifiers in the memory;
the first data unit including the first context identifier and the second data unit including the second context identifier;
the first data unit including data relating to linguistic information in a first one of the terms of the logical formula and the second data unit including data relating to linguistic information in a second one of the terms of the logical formula;
the first context identifier identifying a first context that includes the respective context of each of a first set of one or more disjuncts of the logical formula;
the second context identifier identifying a second context that includes the respective context of each of a second set of one or more disjuncts of the logical formula, the first context applying to the first data unit and the second context applying to the second data unit;
the processor, in executing the second unification instructions, accessing the first data unit and the second data unit and the first and second context identifiers in the memory and using the first and second context identifiers to determine whether to execute the third unification instructions and the fourth unification instructions;
the processor, in executing the third unification instructions, unifying the first and second data units to obtain a unified data unit and storing the unified data unit in the memory;
the processor, in executing the fourth unification instructions, accessing the unified data unit in the memory and using the unified data unit to obtain solution data indicating a solution of the logical formula, the solution data including linguistic information about the logical formula.

15 more elements

at least one of the terms including a disjunction, each disjunction having a plurality of disjuncts, each disjunct having a respective context;
the method being performed with a computer system that includes:
memory;
formula data stored in memory;
the formula data defining the logical formula;
unification instruction data stored in the memory;
the unification instruction data indicating first unification instructions, second unification instructions, third unification instructions, and fourth unification instructions;
and
a processor connected for accessing the memory;
the processor accessing the formula data and the unification instruction data and executing the first unification instructions, the second unification instructions, the third unification instructions, and the fourth unification instructions to solve the logical formula;
the method comprising:
operating the processor to access the unification instruction data and execute the first unification instructions;
the processor, in executing the first unification instructions, accessing the formula data in the memory and using the formula data to produce first and second data units and first and second context identifiers and storing the first and second data units and the first and second context identifiers in the memory;
the first data unit including the first context identifier and the second data unit including the second context identifier;
the first data unit including data relating to linguistic information in a first one of the terms of the logical formula and the second data unit including data relating to linguistic information in a second one of the terms of the logical formula;
the first context identifier identifying a first context that includes the respective context of each of a first set of one or more disjuncts of the logical formula;
the second context identifier identifying a second context that includes the respective context of each of a second set of one or more disjuncts of the logical formula;
the first context applying to the first data unit and the second context applying to the second data unit;
operating the processor to access the unification instruction data and execute the second unification instructions;
the processor, in executing the second unification instructions, accessing the first data unit and the second data unit and the first and second context identifiers in the memory and using the first and second context identifiers to determine whether to execute the third unification instructions and the fourth unification instructions;
operating the processor to access the unification instruction data and execute the third unification instructions;
the processor, in executing the third unification instructions, unifying the first and second data units to obtain a unified data unit and storing the unified data unit in the memory;
operating the processor to access the unification instruction data and execute the fourth unification instructions;
the processor, in executing the fourth unification instructions, accessing the unified data unit in the memory and using the unified data unit to obtain solution data indicating a solution of the logical formula, the solution data including linguistic information about the logical formula.

21 more elements

Dependencies are inferred from the claim text.

Disjunctive unification

Life of this patent

Disjunctive unification

Life of this patent

Abstract

Claims51