Graph Surfing by Reaction Systems

摘要

In this paper, we introduce graph-based reaction systems as a generalization of set-based reaction systems, a novel and well-investigated model of interactive computation. Graph-based reaction systems allow us to introduce a novel methodology for graph transformation, which is not based on the traditional "cut, add, and paste" approach, but rather on moving within a "universe" graph B (surfing on B) from a subgraph of B to a subgraph of B, creating subgraph trajectories within B. We illustrate this approach by small case studies: simulating finite state automata, implementing a shortest paths algorithm, and simulating cellular automata.