A GRAPH REDUCTION SYSTEM USING GRAPH TERMS

A new kind of computing system, a graph reduction system, is introduced using the original notation of graphs. Every graphs and reduction procedures are defined just like as term rewriting systems. Several properties of graphs and graph reductions are studied from the viewpoint of our graph reduction system. Especially, we investigate the ability of parallel reductions and compare parallel reductions with sequential reductions. We formalize the concepts of parallel reductions and sequentially simulatable parallel reductions. Sufficient conditions for reduction rules which guarantees the consistency of parallel reductions and sequential reductions are given. It is also showed that every parallel reduction preserves correctness of solutions for the graph reduction system solving equations of regular expressions