Paper Info
Title
A parameterized graph transformation calculus for finite graphs with monadic branches
Abstract
We introduce a lambda calculus λTFG for transformations of finite graphs by generalizing and extending an existing calculus UnCAL. Whereas UnCAL can treat only unordered graphs, λTFG can treat a variety of graph models: directed edge-labeled graphs whose branch styles are represented by monads T. For example, λTFG can treat unordered graphs, ordered graphs, weighted graphs, probability graphs, and so on, by using the powerset monad, list monad, multiset monad, probability monad, respectively. In λTFG, graphs are considered as extension of tree data structures, i.e. as infinite (regular) trees, so the semantics is given with bisimilarity. A remarkable feature of UnCAL and λTFG is structural recursion for graphs, which gives a systematic programming basis like that for trees. Despite the non-well-foundedness of graphs, by suitably restricting the structural recursion, UnCAL and λTFG ensures that there is a termination property and that all transformations preserve the finiteness of the graphs. The structural recursion is defined in a "divide-and-aggregate" way; "aggregation" is done by connecting graphs with ε-edges, which are similar to the ε-transitions of automata. We give a suitable general definition of bisimilarity, taking account of ε-edges; then we show that the structural recursion is well defined with respect to the bisimilarity.
Year
DOI
Venue
2013
10.1145/2505879.2505903
PPDP
Keywords
Field
DocType
lambda calculus,powerset monad,structural recursion,monadic branch,branch style,probability monad,list monad,parameterized graph transformation calculus,multiset monad,existing calculus uncal,probability graph,unordered graph,finite graph,graph transformation,monad,graph algebra
Modular decomposition,Indifference graph,Computer science,Partial k-tree,Chordal graph,Graph product,Pathwidth,1-planar graph,Calculus,Dense graph
Conference
Citations 
PageRank 
References 
5
0.43
22
Authors
5
Name
Order
Citations
PageRank
Kazuyuki Asada1202.41
Soichiro Hidaka218514.89
Hiroyuki Kato350.77
Zhenjiang Hu4134199.25
Keisuke Nakano521224.62