Hyper-arc consistency in a contraint satisfaction network

Details Hyper-arc consistency in a contraint satisfaction network Hyper-arc consistency in a contraint satisfaction network

2006-08-01

2006-08-01

Hirl, Joseph P. (Department: 2129)

Data processing: artificial intelligence

Adaptive system

C706S012000, C706S046000

Reexamination Certificate

active

07085748

ABSTRACT:
A method for solving a constraint satisfaction problem includes receiving a set of variables having respective input domains and a set of relations among the variables, and building a network of one or more hyper-arcs representative of the set of relations, each hyper-arc corresponding to one of the relations and linking nodes in the network corresponding to the variables that are subject to the relation. For each of the hyper-arcs, the variables are assembled in a hierarchy based on the relation corresponding to the hyper-arc. The input domains of the variables in the hierarchy are reduced, so as to determine respective output domains of the variables that are consistent with the relations.

REFERENCES:
patent: 5617510 (1997-04-01), Keyrouz et al.
patent: 5636328 (1997-06-01), Kautz et al.
patent: 6031984 (2000-02-01), Walser
patent: 6063126 (2000-05-01), Borduin
Alan K. Mackworth, Consistency in Networks of Relations, 1977, North Holland Publishing Company, Artificial Intelligence, 99-118.
Sabin, D. et al., “Understanding and Improving the MAC Algorithm”, Constraint Programming Annual Conference, 1997, pp. 167-181, USA.
Bessiere, C. et al., “Using Constraint Metaknowledge to Reduce Arc Consistency Computation”,Artif. Intell. 107(1), pp. 125-148, 1999.
Dechter, R. et al., “Local and Global Relational Consistency”,Artif. Intell. 41, pp. 273-312, 1990.
Bessiere, C. et al., “Arc Consistency for General Constraint Networks: Preliminary Results”, Proceedings IJCAI, 1997, Negoya, Japan, pp. 398-404.
Bessiere, C. et al., “MAC and Combined Heuristics: Two Reasons to Forsake FC (and CBJ?) on Hard Problems”, Constraint Programming Annual Conference, 1996, pp. 61-75, Cambridge.
Offutt, A.J., “An Integrated Automatic Test Data Generation System”,Journal of Systems Integration, vol. 1, No. 3, Nov. 1991, pp. 391-409, Kluwer Academic Publishers.
Van Beek, P. et al., “On the Minimality and Global Consistency of Row-Convex Constraint Networks”,Journal of ACM, vol. 42, pp. 543-561, 1995.
Marriott, K. et al.,Programming with Constraints: An Introduction, Ch. 3.4, “Bounds Consistency”, the MIT Press, pp. 97-109, 1999.
Mackworth, A., “On Reading Sketch Maps”, IJCAI 1977, pp. 598-606.
Mackworth, A., “Consistency in Networks of Relations”,Artificial Intelligence, vol. 8, 1977, pp. 99-118.
Freuder, E., “A Sufficient Condition for Backtrack-Free Search”,Journal of the Association for Computing Machinery, vol. 29, No. 1, Jan. 1982, pp. 24-32.
Lewin, D., et al., “Constraint Satisfaction for Test Program Generation”,Proc. of the IEEE 14thInt'l Press Conference on Computers and Communic., 1995, pp. 45-48.
Turton, B., “Extending Quine-McCluskey for Exclusive-Or Logic Synthesis”,IEEE Transactions on Education, vol. 39, No. 1, Feb. 1996, pp. 81-85.

Affiliated with

Also associated with

Rating

Hyper-arc consistency in a contraint satisfaction network does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Hyper-arc consistency in a contraint satisfaction network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hyper-arc consistency in a contraint satisfaction network will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3691797