Constraint Reasoning And Constraint Programming Language

Constraint representation, constraint-based reasoning, constraint satisfaction systems and constraint programming languages are important issues in computer science and artificial intelligence. Constraint-based technology can be widely applied to decision supporting, model-based diagnosis, task scheduling, system configuration, the design and analysis of circuit, design of graphics interface, CAD, computer vision, belief maintenance and natural language processing, etc. In this paper, we mainly study constraint-based reasoning from the view points of constraint solving algorithms and constraint languages. We investigate all kinds of approaches for constraint satisfaction problems, and methods of designing and implementing constraint languages. The thesis work are as follows:(1) Investigate various representation framework and paths for solving constraint satisfaction problems, including improved and heuristic algorithms based on backtracking search, logic-based method, automata theory, algebraic approach, connections architecture and genetic algorithm. Compare and analyses features of these approaches. The connection among these paths and the possibility of integrating some of them together is also discussed.(2) Present an improved algorithm for constraint satisfaction problems, namely IBFC. The new algorithm effectively enhances FC+CBJ by incorporating the concept of constraint-based interchangeability. Before solving, the algorithm partitions a variable domain into groups of interchangeable values according to every constraint. During forward-checking, the algorithm processes one group of interchangeable values instead of a value once a time. When it meets dead-end, the algorithm deletes all values from current domain , which belongs to the same equivalent class with the current instantiation. Apart from a small amount of additional overhead of computing...