Contents of Report

[Data of Report]

Report Number:: TR437
Date of Registration:: 1988.11
English Title:: WEIGHTED GRAPHS, a Tool for Studying the Halting Problem and Time Complexity in Term Rewriting Systems and Logic Programming
Japanese Title:: ***
English Author:: P.Devienne
Japanese:
Name of Organization to which author belongs:
PDF:: tr0437.pdf

1	Introduction	.... 2
2	Why Yet Another Syntactic Object?	.... 5
2.1	What is a weighted graph: Informal presentation	.... 6
2.2	Definition of a weighted graph	.... 7
2.3	Interpretation of a weighted graph	.... 8
2.4	Partial order	.... 12
2.5	Unification of finite weighted graphs	.... 13
3	Systems of Equations, Algorithms and Properties	.... 24
3.1	Introduction	.... 24
3.2	Reduced systems of equations	.... 24
3.3	Congruent systems	.... 26
3.4	Minimal systems	.... 28
3.5	Orthogonal systems	.... 31
4	Weighted Graph and Sequence of Global Rewritings	.... 33
4.1	Most general sequence of global rewritings using one rule	.... 33
4.2	Weighted graph and global rewriting rule	.... 34
4.3	Infinite sequence of global rewritings and most general fixpoint	.... 35
4.4	Finite sequence of global rewritings	.... 37
5	Application within the Terms Rewriting Systems, Narrowing and Logic Programming	.... 43
5.1	Global rewriting systems	.... 43
5.2	Global narrowing	.... 43
5.3	Logic programming	.... 44
6	Examples within Logic Programming	.... 48
6.1	Chess game	.... 48
6.2	Commutativity	.... 51
6.3	Function "less than 10" on the natural integers	.... 53
6.4	Occur-Check	.... 54
6.5	Similar patterns, different behaviour	.... 55
7	Conclusion	.... 58
	End	.... 60

目次をクリックすると、PDFファイルが表示されます。