コンピュータサイエンス研究会

2009.03.24

研究会名：コンピュータサイエンス研究会

開催日：平成21年3月24日（火）15:00～17:00

テーマ：“Bidirectionalizing Structural Recursive Transformation on Graphs”

講師：Zhenjiang Hu (National Institute of Informatics)

開催場所：東北大学電気情報系3号館206号室

コンピュータサイエンス研究会講演会の御案内

コンピュータサイエンス研究会
主査　小林直樹

下記のようにコンピュータサイエンス研究会の講演会を開催いたしますので，ご案内申し上げます．

日時：2009年3月24日（火）15:00～17:00
場所：東北大学電気情報系3号館 206号室
題目：“Bidirectionalizing Structural Recursive Transformation on Graphs”
話者：Zhenjiang Hu (National Institute of Informatics)
概要：The bidirectional transformation problem is attracting more and more attention from researchers in programming language community, and there have been many interesting research results dealing with bidirectional transformation on strings or tree-like data structures. However, to the best of our knowledge, none of them can deal with graphs. In this paper, we show that the bidirectional transformation problem on graphs can be well solved, by proposing a bidirectional semantics for an existing graph algebra based on structural recursion called UnCAL,which has been well studied in the database community as an underlying algebra of more user-friendly syntax called UnQL graph query language.Challenges in graph transformation come from the cyclic nature of data model. We solve the problem by making use of original bulk semantics of structural recursion in which individual edge and reachable parts thereof can be independently transformed to reorganize the result. The bulk semantics also plays an important role in dealing with insertion of new graphs into the target, since which portion in the source to propagate the new graph can be relatively easily determined using the semantics. A prototype system has been implemented and is available online, and the experimental results show the usefulness of our approach.
This is a joint work with Soichiro Hidaka, Hiroyuki Kato and Keisuke Nakano.