Marker-directed optimization of UnCAL graph transformations

Soichiro Hidaka, Zhenjiang Hu, Kazuhiro Inaba, Hiroyuki Kato, Kazutaka Matsuda, Keisuke Nakano, Isao Sasano

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Citations (Scopus)


Buneman et al. proposed a graph algebra called UnCAL (Unstructured CALculus) for compositional graph transformations based on structural recursion, and we have recently applied to model transformations. The compositional nature of the algebra greatly enhances the modularity of transformations. However, intermediate results generated between composed transformations cause overhead. Buneman et al. proposed fusion rules that eliminate the intermediate results, but auxiliary rewriting rules that enable the actual application of the fusion rules are not apparent so far. UnCAL graph model includes the concept of markers, which correspond to recursive function call in the structural recursion. We have found that there are many optimization opportunities at rewriting level based on static analysis, especially focusing on markers. The analysis can safely eliminate redundant function calls. Performance evaluation shows its practical effectiveness for non-trivial examples in model transformations.

Original languageEnglish
Title of host publicationLogic-Based Program Synthesis and Transformation - 21st International Symposium, LOPSTR 2011, Revised Selected Papers
Number of pages16
Publication statusPublished - 2012
Event21st International Symposium on Logic-Based Program Synthesis and Transformation, LOPSTR 2011 - Odense, Denmark
Duration: 2011 Jul 182011 Jul 20

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7225 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference21st International Symposium on Logic-Based Program Synthesis and Transformation, LOPSTR 2011


  • UnCAL
  • graph transformations
  • program transformations

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Marker-directed optimization of UnCAL graph transformations'. Together they form a unique fingerprint.

Cite this