Implementation of the Hierarchical Graph Rewriting Language LMNtal.

Kei Murayama, Shintaro Kudo, Ken Sakurai, Ken Mizuno, Norio Kato, Kazunori Ueda

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


LMNtal is a language model based on hierarchical graph rewriting that allows the representation and the manipulation of connectivity expressed using links and hierarchy expressed using membranes. The model allows concise description of programs involving dynamic data structures and multiset processing. Since LMNtal features fine-grained concurrency whose atomic operation is the application of a rewrite rule, how to implement it correctly and efficiently is far from obvious. This motivated us to implement LMNtal using Java and establish implementation techniques that are both correct and reasonably efficient. Our implementation consists of a compiler into intermediate code, an interpreter of the intermediate code, and a translator from the intermediate code to Java source code. It also provides a variety of useful features including foreignlanguage interface. The cruxes of the implementation techniques include the handling of links that cross membranes and the asynchronous execution of rewrite rules belonging to different membranes. This paper describes the design and implementation of our publicly available LMNtal system, focusing on technical issues raised in the course of the development. Those issues include the representation of hierarchical graph structures, intermediate code, and safe asynchronous execution of multiple tasks.

Original languageEnglish
Pages (from-to)47-77
Number of pages31
JournalComputer Software
Issue number2
Publication statusPublished - 2008 Jan

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Implementation of the Hierarchical Graph Rewriting Language LMNtal.'. Together they form a unique fingerprint.

Cite this