Graph Transformation as Graph Reduction FUnCAL: A Functional Reformulation of Graph-Transformation Language UnCAL
Kazutaka Matsuda, Kazuyuki Asada · 2015
A large amount of graph-structured data are widely used, including biological database, XML with IDREFs, WWW, and UML diagrams in software engineering. UnCAL, proposed by Buneman et al. from the database community, is a language designed for graph transformations, i.e., extracting a subpart of a graph data and converting it to a suitable form, which often also has a graph structure. A distinguished feature of UnCAL is its semantics that respects bisimulation on graphs; this enables us to reason about UnCAL graph transformations as recursive functions, which is useful for verification as well as optimization. However, despite of this similarity of UnCAL to functional languages, there is still a gap to apply the program-manipulation techniques studied in the programming language literature directly to UnCAL programs, due to some special features in UnCAL, especially markers. In this paper, first, we give a translation from UnCAL programs to functional ones by emulating markers by tuples and