摘要: We introduce term graph narrowing as an approach for solving equations by transformations on graphs. Term combines rewriting with first-order unification. Our main result is that this mechanism complete all systems over which normalizing and confluent. This includes, in particular, convergent systems. Completeness means every solution of a given equation, can find more general solution. The motivation using graphs instead terms to improve efficiency: sharing common subterms saves space avoids the repetition computations.
sci-hub.se 参考文章(14)
Berthold Hoffmann, Detlef Plump, Implementing term rewriting by jungle evaluation Theoretical Informatics and Applications. ,vol. 25, pp. 445- 472 ,(1991) , 10.1051/ITA/1991250504451
A. Habel, Hyperedge Replacement: Grammars and Languages ,(1992)
Jean-Marie Hullot, Canonical forms and unification 5th Conference on Automated Deduction Les Arcs, France, July 8–11, 1980. pp. 318- 334 ,(1980) , 10.1007/3-540-10009-1_25
Detlef Plump, Collapsed Tree Rewriting: Completeness, Confluence, and Modularity CTRS '92 Proceedings of the Third International Workshop on Conditional Term Rewriting Systems. pp. 97- 112 ,(1992) , 10.1007/3-540-56393-8_7
Detlef Plump, Critical Pairs in Term Graph Rewriting mathematical foundations of computer science. pp. 556- 566 ,(1994) , 10.1007/3-540-58338-6_102
Detlef Plump, Annegret Habel, Graph Unification and Matching international workshop on graph-grammars and their application to computer science. pp. 75- 88 ,(1994) , 10.1007/3-540-61228-9_80
Andrea Corradini, Dietmar Wolz, Jungle Rewriting: an Abstract Description of a Lazy Narrowing Machine Proceedings of the International Workshop on Graph Transformations in Computer Science. pp. 119- 137 ,(1993) , 10.1007/3-540-57787-4_8
Aart Middeldorp, Erik Hamoen, Completeness results for basic narrowing Applicable Algebra in Engineering, Communication and Computing. ,vol. 5, pp. 213- 253 ,(1994) , 10.1007/BF01190830
Michael Hanus, The Integration of Functions into Logic Programming: From Theory to Practice Journal of Logic Programming. pp. 583- 628 ,(1994) , 10.1016/0743-1066(94)90034-5
Annegret Habel, Detlef Plump, Unification, Rewriting, and Narrowing on Term Graphs Electronic Notes in Theoretical Computer Science. ,vol. 2, pp. 110- 117 ,(1995) , 10.1016/S1571-0661(05)80187-2