« Computation Model CCM, Based on Production Rules and Local Evaluation Functions -- Its Extension and Application to 0-1 Integer Programming Problems -- | Main | Stochastic Problem Solving by Local Computation based on Self-organization Paradigm »

Various Sorting Methods by CCM, a Computational Model Based on Production Rules and Local Evaluation Functions

Kanada, Y., SIG Notes on Symbol Processing, Information Processing Society of Japan, 93-SYM-71-5, pp. 33-40, 1993, Published by IPSJ

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

[ Sort and N queens problem demo in Java (Only one type of sorting) ]

Abstract: The author has proposed the Chemical Casting Model (CCM), which is a stochastic computation model whose elements are production rules and evaluation functions that are computed only using local information, and has proposed a computation language SOOC based on CCM. This model is targeted to apply to problems on open systems in which even specifications cannot be clearly written down. However, it is also important to make experiment on applying this model to conventional problems. Thus, CCM is applied to sorting in this paper, and a new sorting method is presented and several sorting methods based on conventional methods, i.e., insertion sort and exchange sort, are presented. The results of experiments are also shown. By these methods, sorting can be done only using one production rule and one evaluation function both of which only refer to local information. Several interesting phenomena caused by computation only using local information are also mentioned.

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

Keywords: CCM, Sorting, Emergent computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Production system, Production rule, Local evaluation function

Post a comment


This page contains a single entry from the blog posted on November 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