(92) Constraint MGTP (Prolog version/KL1 version /KLIC version)

	Machine:     PIM/UNIX machine
	Environment: PIMOS/UNIX, KLIC
	Language:    Prolog/KL1
	Source Code: 0.2 MB
	Documents:   Manual (English / Japanese)

Overview

Extended MGTP to solve finite domain constraint satisfaction problems.

Features

negative atoms can be used to represent negative information propagation,
the integrity constraint ( unit refutation ), is introduced,
extended MGTP rules, such as and are added to the original rule ,
unit simplification is performed between atoms in the model candidate set and disjunctions in the model-extending candidate set.

Function

Although finite domain constraint satisfaction problems can be described in concise descriptions as MGTP input clauses, MGTP has the demerit that it cannot propagate negative constraints since it is based on forward reasoning and only uses positive atoms, and cannot prune a lot of redundant branches.

To overcome this in CMGTP, we can use negative atoms to represent negative constraint propagation, and the following unif refutation and unit simplification mechanism are introduced to prune redundant branches:

where M, D shows model candidate set, and model extending candidate set respectively.

CMGTP can be considered as a meta language to describe constraint propagation rules directly.

We have tried to solve quasigroup existence problems in finite algebra using CMGTP. CMGTP can solve them more efficiently than other constraints solvers.

FTP

README.
Constraint MGTP (Prolog version/KL1 version /KLIC version) [597K]

www-admin@icot.or.jp