Data processing: artificial intelligence – Knowledge processing system – Knowledge representation and reasoning technique
Reexamination Certificate
2007-01-16
2007-01-16
Hirl, Joseph P (Department: 2129)
Data processing: artificial intelligence
Knowledge processing system
Knowledge representation and reasoning technique
C706S053000, C706S012000
Reexamination Certificate
active
10073934
ABSTRACT:
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.
REFERENCES:
patent: 5228115 (1993-07-01), Natarajan
patent: 5438511 (1995-08-01), Maxwell et al.
patent: 5727222 (1998-03-01), Maxwell, III
patent: 5819210 (1998-10-01), Maxwell, III et al.
patent: 5903860 (1999-05-01), Maxwell, III et al.
patent: 6064953 (2000-05-01), Maxwell, III et al.
patent: 6085186 (2000-07-01), Christianson et al.
patent: 6102969 (2000-08-01), Christianson et al.
Gregory M. Provan et al, Model-Based Object Recognition: A Truth Maintenance Approach, Mar. 1988, IEEE, ch2552-8/88/0000/0230, 230-235.
Eugene C. Freuder, “A Sufficient Condition for Backtrack-Bounded Search,” Journal of the Association of Computing Machinery, vol. 32, No. 4, pp. 755-761, Oct. 1985.
Rina Dechter et al., “Network-Based Heuristics for Constraint-Satisfaction Problems,” Artificial Intelligence 34, pp. 1-38, 1988.
Johan de Kleer, “An Assumption-based TMS,” Artificial Intelligence 28, pp. 127-162, 1986.
Johan de Kleer, “Extending the ATMS,” Artificial Intelligence 28, pp. 163-196, 1986.
Jeffrey Mark Siskind, “The Culprit Pointer Method for Selective Backtracking,” Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Jan. 1989.
Hirl Joseph P
Oliff & Berridg,e PLC
LandOfFree
Systems and methods for solving nogood databases does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systems and methods for solving nogood databases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods for solving nogood databases will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3802027