Presentation 2014-07-29
Evaluation of Large-scale Graph Rewriting Model Checking Using Hash Compaction
Taketo YOSHIDA, Masaru ONUMA, Kazunori UEDA,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) Graph rewriting model checking is a verification method that determines whether a model described in a graph rewriting system satisfies required properties by exploring all reachable states. Graph rewriting has a high expressive power in representing information structures of models. This often results in the reduction of the number of states in model checking. On the other hand, graphs are heavyweight data structures in terms of both space and time. In this study, we implemented a Hash Compaction method to improve space and time efficiency of the LMNtal parallel model checker SLIM and measured its performance. Since Hash Compaction does not guarantee the reproduction of complete state space, we also studied and evaluated the effect of the accuracy of the hash function on the state space.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) Model Checking / Hash Compaction / Graph Rewriting
Paper # DC2014-19
Date of Issue

Conference Information
Committee DC
Conference Date 2014/7/22(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To Dependable Computing (DC)
Language JPN
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) Evaluation of Large-scale Graph Rewriting Model Checking Using Hash Compaction
Sub Title (in English)
Keyword(1) Model Checking
Keyword(2) Hash Compaction
Keyword(3) Graph Rewriting
1st Author's Name Taketo YOSHIDA
1st Author's Affiliation Graduate School of Fundamental Science and Engineering, Waseda University()
2nd Author's Name Masaru ONUMA
2nd Author's Affiliation Graduate School of Fundamental Science and Engineering, Waseda University
3rd Author's Name Kazunori UEDA
3rd Author's Affiliation Graduate School of Fundamental Science and Engineering, Waseda University
Date 2014-07-29
Paper # DC2014-19
Volume (vol) vol.114
Number (no) 156
Page pp.pp.-
#Pages 8
Date of Issue