論文

査読有り
2013年9月

Structural Recursion for Querying Ordered Graphs

ACM SIGPLAN NOTICES
  • Soichiro Hidaka
  • ,
  • Kazuyuki Asada
  • ,
  • Zhenjiang Hu
  • ,
  • Hiroyuki Kato
  • ,
  • Keisuke Nakano

48
9
開始ページ
305
終了ページ
318
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1145/2500365.2500608
出版者・発行元
ASSOC COMPUTING MACHINERY

Structural recursion, in the form of, for example, folds on lists and catamorphisms on algebraic data structures including trees, plays an important role in functional programming, by providing a systematic way for constructing and manipulating functional programs. It is, however, a challenge to define structural recursions for graph data structures, the most ubiquitous sort of data in computing. This is because unlike lists and trees, graphs are essentially not inductive and cannot be formalized as an initial algebra in general. In this paper, we borrow from the database community the idea of structural recursion on how to restrict recursions on infinite unordered regular trees so that they preserve the finiteness property and become terminating, which are desirable properties for query languages. We propose a new graph transformation language called lambda(FG) for transforming and querying ordered graphs, based on the well-defined bisimulation relation on ordered graphs with special epsilon-edges. The language lambda(FG) is a higher order graph transformation language that extends the simply typed lambda calculus with graph constructors and more powerful structural recursions, which is extended for transformations on the sibling dimension. It not only gives a general framework for manipulating graphs and reasoning about them, but also provides a solution to the open problem of how to define a structural recursion on ordered graphs, with the help of the bisimilarity for ordered graphs with epsilon-edges.


リンク情報
DOI
https://doi.org/10.1145/2500365.2500608
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000327696700029&DestApp=WOS_CPL
ID情報
  • DOI : 10.1145/2500365.2500608
  • ISSN : 0362-1340
  • eISSN : 1558-1160
  • Web of Science ID : WOS:000327696700029

エクスポート
BibTeX RIS