$\newcommand{\defeq}{\mathrel{\mathop:}=}$

## 2008/04/29

### Half of the Hylomorphism Theorem

The Hylomorphism Theorem states that a hylomorphism is the least fixed point of a certain equation. Its proof is divided into two parts: one proving that a hylomorphism is a fixed point, and the other proving that a hylomorphism is a lower bound of all fixed points. The second part is what we need in the proof of the Greedy Theorem, and that was what I was working on (and finished) tonight. Since the proof consists of only "ordinary" arrows and composition, the entire process was quite a pleasure, even when one need to explicitly specify associativity of relation composition and various kinds of monotonicity. I haven't pushed it into the repository since the symbol for converse was changed (among others?) and I need to resolve some conflicts.

--
It is very likely that the Greedy Theorem will be proven soon.

Labels:

yen34/30/2008 12:23 am 說：

yen34/30/2008 12:27 am 說：

btw Greedy Theorem和Greedy Algorithm有關係嗎?

Josh Ko4/30/2008 12:44 am 說：

Greedy Theorem 導出的演算法傳統上有時候會被視為 dynamic programming algorithms。實際與傳統的 greedy algorithms 重疊的程度我還不太清楚。（看 scm 老師有沒有興趣講解一下 XD。）

yen34/30/2008 1:18 am 說：

scm5/01/2008 8:10 am 說：

Comment 的篇幅好像只能大概說明一下耶.. :)