« Symbolic Random Tunneling Based on Composing Production Rules -- Constraint Satisfaction and Optimization Using Computation Model CCM -- | Main | The Effects of Randomness in Asynchronous 1D Cellular Automata »

Dynamic Graph Coloring using CCM -- A Model for Emergent Computation

Kanada, Y., SIG Note of Parallel Procesing of Artificial Intelligence, The Society of Artificial Intelligence, SIG-PPAI-9401, pp. 7-12, 1994, Published by JSAI.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file: Part 1, Part 2 (in Japanese) ]
[ Poster postscript file: Part 1, Part 2 ]
[ Poster PDF file : Part 1, Part 2 ]

[ Coloring demo in Java (static coloring) ]

Abstract: Real world computing systems are complex systems that is open to the continually varying environment. Conventional software development methods inherently cannot deal such situations. CCM (Chemical Casting Model) is a model of nondeterministic, or random, computation, which is based on local information. CCM is developed toward establishing a software development methodology based on emergent computation. CCM is a production system with locally computed evaluation functions. A method of coloring vertices of dynamically changing graphs, or a method of radio-wave assignments to moving stations, by using SOOC -- a CCM-based computation language, is explained, and the results of experiments are shown in the present report. Dynamic coloring can be performed using the same production rule and evaluation function as static coloring, and the results can be evaluated using basically the same method and tools.

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

Keywords: CCM, Dynamic constraint satisfaction problem, Emergent Computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving

Post a comment


This page contains a single entry from the blog posted on April 1, 1994 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