2012/01/26 by Areski Nait Abdallah, M. H. van Emden, Abdallah, A. Nait +1
Computer Science · #AI-based Problem Solving and Planning #Artificial Intelligence (cs.AI) #Constraint Satisfaction and Optimization #D.3.3 #Data Management and Algorithms #F.3.2 #FOS: Computer and information sciences #G.1.0
paper · pdf · doi:10.48550/arxiv.1201.5426
openalex publication_date 2012/01/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper draws on diverse areas of computer science to develop a unified view of computation: (1) Optimization in operations research, where a numerical objective function is maximized under constraints, is generalized from the numerical total order to a non-numerical partial order that can be interpreted in terms of information. (2) Relations are generalized so that there are relations of which the constituent tuples have numerical indexes, whereas in other relations these indexes are variables. The distinction is essential in our definition of constraint satisfaction problems. (3) Constraint satisfaction problems are formulated in terms of semantics of conjunctions of atomic formulas of predicate logic. (4) Approximation structures, which are available for several important domains, are applied to solutions of constraint satisfaction problems. As application we treat constraint satisfaction problems over reals. These cover a large part of numerical analysis, most significantly nonlinear equations and inequalities. The chaotic algorithm analyzed in the paper combines the efficiency of floating-point computation with the correctness guarantees of arising from our logico-mathematical model of constraint-satisfaction problems.