« Symbol Processing as Stochastic Processes - Macroscopic Models of Computation Processes -- | Main | Features of Problem-Solving Method using Computation Model CCM, based on Production Rules and Local Evaluation Functions »

A Method of Solving Constraint Satisfaction Problems using Production Rules and Local Evaluation Functions

Kanada, Y., and Hirokawa, M.: , SIG Notes of Symbol Processing, Information Processing Society of Japan, 93-SYM-68-2, 1993, Published by IPSJ.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file (in Japanese) ]
[ OHP postscript file: Slides, Handout ]
[ OHP PDF ファイル: Slides, Handout ]

[ N queens problem demo in Java ]

Abstract: The authors have proposed the Chemical Casting Model (CCM), which is a computation model for self-organizing computation. In this model, "programs" consist of a few production rules and evaluation functions (or local order degrees), both of which only refer to local information. A method of solving certain constraint-satisfaction problems, based on this model, is presented in this paper. This method enables to solve constraint-satisfaction problems, such as the N-queens problems or map coloring problems, in a polynomial order time, without using deterministic and procedural constraint propagation, but using a stochastic method, and by a very simple "program." This paper also mentions to the characteristics of the computation by on this method, based on several measurements.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Constraint satisfaction problem, Emergent Computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Local information, Localized computation, Local evaluation function, Production system, N queens problem, Coloring problem

Post a comment


This page contains a single entry from the blog posted on March 1, 1993 12:00 AM.

Many more can be found on the main index page or by looking through the archives.

(C) Copyright 2007 by Yasusi Kanada
Powered by
Movable Type 3.36