Evolution of the LMNtal runtime to a parallel model checker

Masato Gocho*, Taisuke Hori, Kazunori Ueda

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


Model checking is a verification technique based on the exhaustive search of erroneous behaviors of state transition systems, which is attracting growing interest. The LMNtal language allows us to represent state transition systems using hierarchical graph rewriting, and its runtime system, SLIM, has recently evolved into an explicit-state model checker. Hierarchical graphs are a powerful data structure that features a builtin symmetry reduction mechanism that plays a key role in state space search. However, model checking is still prone to state space explosion and has called for time- and space-efficient methods for state management. To address this problem and make our model checker more useful, we have extended the SLIM runtime further to a parallel model checker to run on shared-memory multiprocessors and developed various optimization techniques of state management. These two enhancements drastically improved the scale of problems the LMNtal model checker can handle as well as its performance.

Original languageEnglish
Pages (from-to)137-157
Number of pages21
JournalComputer Software
Issue number4
Publication statusPublished - 2011

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Evolution of the LMNtal runtime to a parallel model checker'. Together they form a unique fingerprint.

Cite this