|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc010205,
author = {Peter Hartmann},
title = {Implementation of Parallel Replacement Systems for
Cellular Hypergraphs},
journal = jalc,
year = 1996,
volume = 1,
number = 2,
pages = {129--146},
keywords = {multidimensional and dynamic cellular structures,
graph replacement systems, relative spatial addressing,
subgraph matching},
abstract = {This paper gives an overview about the concept of cellular
hypergraphs and parallel replacement systems for these
graphs. A versatile addressing model is presented which can
be used to perform computations on state values associated
with a graph. The same addressing model is the key to an
efficient subgraph matching algorithm. This algorithm
demonstrates that the presented concept can be applied
to real world problems. Cellular hypergraphs with
replacement systems are a generalization of the cellular
automata (CA) paradigm which constitutes an inherently
massive-parallel model of computation. The usage of a set
of productions instead of a CA's local transition function
allows us not only to formulate state transitions, but
furthermore temporal modifications of the cellular structure
itself. Consequently the concept can be used as an abstract
model of computation for those applications which are based
on irregular and dynamically changing meshes, i.e. the
simulation of biological systems, dynamic sceneries in
computer graphics and adaptive mesh generation algorithms.}
}