For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Graph Rewriting Systems and Their Application to Network Reliability Analysis
Yasuyoshi OKADA Masahiro HAYASHI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1993/02/25
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)>>
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.