Systems and methods for solving nogood databases
View Patent ↗Systems and methods for solving nogood databases involve generating a representation comprising a plurality of contexted disjunctions, conjoining all of the contented disjunctions to form a conjunction of contexted disjunctions, and storing the representation as the conjunction of contexted disjunctions. Nogoods are eliminated by refining the representation until a result of the conjunction of contexted disjunctions is backtrack-free or the result of the conjunction of contexted disjunctions reduces to false. In various embodiments, the refining is carried out without reordering the disjunctions and/or without merging the disjunctions. In various embodiments, the systems and methods are used for various constraint satisfaction problems, such as syntactic processing of natural language sentences, map coloring, understanding line drawings, electronic circuit analysis, and truth maintenance systems.
1. A method for solving nogood databases within a natural language constraint satisfaction problem, comprising:
generating a representation of possible solutions to the problem comprising a plurality of contexted disjunctions;
conjoining all of the contexted disjunctions by anding the contexted disjunctions together to form a conjunction of contexted disjunctions;
storing the representation as the conjunction of contexted disjunctions; and
eliminating nogoods by refining the representation until a result of the conjunction of contexted disjunctions is backtrack-free or the result of the conjunction of contexted disjunctions reduces to false, a nogood being a prepositional variable or a conjunction of prepositional variables whose constraints are unsatisfiable in the context of the problem.
2. The method of claim 1 , wherein refining the representation is carried out without reordering the disjunctions.
3. The method of claim 1 , wherein refining the representation is carried out without merging the disjunctions.
4. The method of claim 1 , further comprising transforming the representation so that the conjunction of contexted disjunctions is backtrack-free.
5. The method of claim 4 , wherein transforming the representation is carried out without reordering the disjunctions.
6. The method of claim 4 , wherein transforming the representation is carried out without merging the disjunctions.
7. The method of claim 1 , further comprising transforming the representation so that choosing any disjunct from each of the disjunctions results in a valid solution.
8. The method of claim 7 , wherein transforming the representation is carried out without reordering the disjunctions.
9. The method of claim 7 , wherein transforming the representation is carried out without merging the disjunctions.
10. The method of claim 1 , further comprising:
solving a nogood database using the representations, the nogood database comprising at least one nogood.
11. The method of claim 1 , wherein a nogood is a propositional variable or a conjunction of propostional variables whose associated constraints are unsatisifable.
12. The method of claim 1 , the method further comprising:
outputting the result to a user, the natural language constraint satisfaction problem being a natural language parsing constraint satisfaction problem.
13. The method of claim 1 , the method further comprising:
outputting the result to a user, the natural language constraint satisfaction problem being a natural language translation constraint satisfaction problem.
14. A system for solving nogood databases within a natural language constraint satisfaction problem, comprising:
a storage device that stores a representation comprising a plurality of contexted disjunctions; and
a processor that:
conjoins all of the contexted disjunctions to form a conjunction of contexted disjunctions and replaces the representation with the conjunction of contexted disjunctions; and
eliminates nogoods by refining the representation until a result of the conjunction of contexted disjunctions is backtrack-free or the result of the conjunction of contexted disjunctions reduces to false, a nogood being a prepositional variable or a conjunction of prepositional variables whose constraints are unsatisfiable in the context of the problem.
15. The system of claim 14 , further comprising a processor that transforms the representation so that the conjunction of contexted disjunctions is backtrack-free.
16. The system of claim 14 , further comprising a processor that transforms the representation so that choosing any disjunct from each of the disjunctions results in a valid solution.
17. A method for solving nogood databases within a natural language constraint satisfaction problem, comprising:
generating a representation comprising a plurality of contexted disjunctions;
conjoining all of the contexted disjunctions to form a conjunction of contexted disjunctions;
storing the representation as the conjunction of contexted disjunctions; and
eliminating nogoods by setting a first nogood to be a current nogood and repeating the steps of:
(a) if there is no current nogood, stopping further execution of the eliminating nogoods step,
(b) creating a list of relevant disjunctions,
(c) setting a current disjunction to a first disjunction in the list of relevant disjunctions,
(d) if there is no current disjunction, returning to step (a),
(e) splitting the current disjunction into two mutually exclusive disjunctions based on the current nogood,
(f) pruning the nogood disjuncts from the current nogood,
(g) if the current nogood is not empty, going forward to step (i),
(h) adding a context of the current nogood to the nogood database, and
(i) making the next disjunction the current disjunction and returning to step (d),
until a result of the conjunction of contexted disjunctions is backtrack-free or the result of the conjunction of contexted disjunctions reduces to false, a nogood being a prepositional variable or a conjunction of prepositional variables whose constraints are unsatisfiable in the context of the problem.