Natural Constraint Language

NCL (Natural Constraint Language) is a description language with mathematical logic as syntax. It adopts Mixed Set Programming as algorithmic framework for modeling and solving problems.
Introduction
Combinatorial problems are ubiquitous in the daily life and work. Being usually NP-hard, they are in general very difficult to solve. The goal of designing NCL is to provide a programming language that is close to basic human reasoning which could be to a large extent symbolized by conventional mathematical logic. In this sense, NCL is a description language with context-sensitive (while not context-free) grammar for solving constraint satisfaction problems. Consequently, NCL supports implicit typing and context-based constraint reasoning and solving.
Features
NCL stems from Constraint Programming. However its basic differences from CP systems and script style modeling languages are two-fold:
* At the parser level: NCL’s “Semantic Parser” understands natural problem formulation in mathematical logic and submits abstract models to its solver. Technically saying, NCL's syntax is context-sensitive, not context-free.
* At the solver level: Mixed Set Programming solves problems over a mixed domain of reals, integers, Booleans, references, dates/times and sets. The solver incorporates a simplified form of first order logic, naïve set reasoning, numerical constraints, date/time management and operations research algorithms to solve problems in a cooperative manner.
Traditional CP systems strengthen problem modeling and solving capability by introducing OR algorithms called “global constraints”. For comparison, in NCL no special predicate such as Sort, Alldifferent, Alldisjoint, Cumulative, Cycle/Path, Sequencing, Global Cardinality/Among/Distribute, etc. is introduced, though NCL includes algorithms for solving these related problems and many others. Global Constraints do not fit in NCL due to two reasons:
* Besides hundreds of elementary algorithms, several tens of “big” algorithms such as “sort” exist in NCL. Even “sort” alone has at least four variants for each of the domains of reals, integers and sets, and may be linked to peripheral concepts such as “UnaryResource”, “AscendingSorting”, “RegretBasedSearch”, etc. This suggests that global (or specialized) constraints cannot be explicitly defined in NCL. Otherwise too many specific names and peripheral concepts will be introduced.
* From a global point of view, context-based reasoning and solving is crucial. Sophisticated reasoning links between algorithms are the key to solving complex problems. This suggests that there should be some mechanism beyond “global constraints” to support context-based analysis and coordination for embedded algorithms. In NCL, “Semantic Parser” recognizes mathematical logic formulation, identifies algorithms and coordinates algorithmic links for solving a problem.

Main Menu

See Also

Main Menu