SOLVING CONSTRAINT SATISFACTION PROBLEMS FOR USER INTERFACE AND SEARCH ENGINE

• US 20100324888A1
• Filed: 12/25/2008
• Published: 12/23/2010
• Est. Priority Date: 12/27/2007
• Status: Active Grant

• Current Assignee: Assaf Rachamim
• Original Assignee: Assaf Rachamim
• Inventors: Rachamim, Assaf
• Granted Patent: US 8,321,200 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G10L 15/19 Grammatical context, e.g. disambiguation of the recognition hypotheses based on word sequence rules

Abstract

A method for interpreting a Natural Language by an artificial construct using constraint satisfaction problem solving, comprises a) providing a plurality of ways suitable to define at least a grammar for at least a Natural Language, b) providing a plurality of constraint satisfaction problem instructions c) providing a plurality of values for solving a plurality of constraints, d) converting said plurality of constraints to at least one constraint satisfaction problem pattern, e) receiving a Natural Language construct, f) unifying said plurality of constraints through said at least one constraint satisfaction problem pattern at execution runtime by the artificial construct to solve theconstraint satisfaction problem, g) interpreting said Natural Language construct according to a plurality of constraint satisfaction problem instructions, and h) answering to a Natural Language construct by a Natural Language construct.

Claims

1. A method for interpreting a Natural Language by an artificial construct using constraint satisfaction problem solving, comprising:

a) providing a plurality of ways suitable to define at least a grammar for at least a Natural Language;

b) providing a plurality of constraint satisfaction problem instructions, wherein at least one instruction relates to at least a grammar of at least a Natural Language;

c) providing a plurality of values for solving a plurality of constraints, wherein at least one set of zero or more values is provided during the interpreting process by the artificial construct;

d) converting said plurality of constraints to at least one constraint satisfaction problem pattern, wherein said at least one constraint satisfaction problem pattern has a plurality of versions;

e) receiving a Natural Language construct;

f) Unifying said plurality of constraints through said at least one constraint satisfaction problem pattern at execution runtime by the artificial construct to solve the constraint satisfaction problem, wherein said unifying is performed sequentially on each version of said plurality of versions until said constraint satisfaction problem is solved;

g) interpreting said Natural Language construct according to a plurality of constraint satisfaction problem instructions, wherein said interpretation comprises unification; and

h) answering to a Natural Language construct by a Natural Language construct;

wherein said Natural Language is not restricted to any fixed language structure nor to a specific vocabulary or predefined dictionary or collection of words.

2. The method of claim 1, wherein said unifying step produces at least an object based on a plurality of constraints.

3. The method of claim 2, wherein each version of an object and its of said at least one related constraint satisfaction problem pattern comprises a plurality of conditions, and wherein said unifying process of said plurality of conditions comprises evaluating each condition to determine its validity, such that said unifying is performed until all conditions of a version are valid or until no further versions are available.

4. The method of claim 3, wherein at least one condition comprises at least one argument for determining the validity of said condition.

5. The method of claim 4, wherein at least one condition comprises at least one operator for determining a relationship between said plurality of arguments.

6. The method of claim 5, wherein said artificial construct comprises a hosting environment language for the implementation of said instructions.

7. The method of claim 1, wherein at least one condition is obtained from said hosting environment language.

8. The method of claim 7, wherein at least one condition comprises a constraint satisfaction problem pattern.

9. The method of claim 8, wherein at least one condition comprises a placeholder for receiving a value at evaluation process for unification step.

10. The method of claim 9, wherein a placeholder comprises an object.

11. The method of claim 12, wherein said object has a type and said unifying is performed according to said object type.

12. The method of claim 1, wherein at least one condition comprises an alternative version of at least one constraint satisfaction problem pattern.

13. The method of claim 1, wherein said value for said placeholder is selected from a plurality of values.

14. The method of claim 13, wherein said value for said placeholder is selected from a unification environment.

15. The method of claim 14, wherein said unification environment comprises a plurality of objects.

16. The method of claim 15, wherein said plurality of objects comprises objects at least a remote location from the artificial construct and local to the artificial construct.

17. The method of claim 16, wherein said remote location comprises a location on a computer network, wherein the artificial construct communicates with said remote location through said computer network.

18. The method of claim 1, wherein said plurality of objects is accessed according to a priority access order.

19. The method of claim 1, wherein said unification environment is modified at the evaluation process of said instructions.