Graph Rewriting Systems and Their Application to Network Reliability Analysis

Yasuyoshi OKADA  Masahiro HAYASHI  

IEICE TRANSACTIONS on Information and Systems   Vol.E76-D   No.2   pp.154-162
Publication Date: 1993/02/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Automaton, Language and Theory of Computing
graph rewriting systems,  critical pair lemma,  complete systems,  reduction methods,  network reliability,  

Full Text: PDF(685.3KB)>>
Buy this Article

We propose a new type of Graph Rewriting Systems (GRS) that provide a theoretical foundation for using the reduction method which plays an important role on analyze network reliability. By introducing this GRS, several facts were obtained as follows: (1) We clarified the reduction methods of network reliability analysis in the theoretical framework of GRS. (2) In the framework of GRS, we clarified the significance of the completeness in the reduction methods. (3) A procedure of recognizing complete systems from only given rewriting rules was shown. Specially the procedure (3) is given by introducing a boundary graph (B-Graph). Finally an application of GRS to network reliability analysis is shown.