Constructive Negation

Inclusion of negation into logic programs is considered traditionally to be painful as the incorporation of full logic negation tends to super-exponencial time complexity of the prover. Therefore the alternative approaches to negation in logic programs are studied and among them, the procedural negation as failure sounds to be the most successful and the most widely used.

With the spread of Constraint Logic Programming (CLP), the other approach called constructive negation becomes more popular. The reasons for acceptance of constructive negation are the preservation of the advantages of the negation as failure, i.e., efficiency and handling special features of the language, and, at the same time, removing the main drawbacks, i.e., handling ground negative subgoals and usage as a test only.

The Aim of the Project

The aim of the project is to provide a framework for natural implementation of constructive negation. Currently, we investigate the possibility to extend the proposed framework to Hierarchical Constraint Logic Programming. The project covers:
  • theoretical background (solving equalities and disequalities over the Herbrand Universe)
  • methodology
  • implementation



To test our research ideas we have implemented the proposed algorithms in Prolog. Note that these programs are software prototypes.

Meta-variables (1996)

There is a PROLOG implementation of the meta-variable concept originated from ECRC. With this module you can use meta-variables in "normal" PROLOG.

Constructive negation (1994)

The program implements a constructive negation using the concept of meta-interpreters. It is a refined version of program from my Master Thesis.



Constructive Negation and Constraints (download)
Barták, R., Extended Abstract, July 1998

Constructive Negation in CLP(H) (download)
Barták, R., Tech. Report No 98/6, Department of Theoretical Computer Science, Charles University, Prague, July 1998


The project is supported in part by:
  • Faculty of Mathematics and Physics, Charles University
  • Grant Agency of Czech Republic under the contract No 201/96/0197.

The other supporters are very welcomed, especially from the industry area. If you want to support this project (and exploit the research results directly), please contact me.

Constraints] [Negation] [Meta-interpreters] [Media Analysis]

[Search] [Guides]

Charles University
Malostranské nám. 25
Praha 1