Proof Pearl: Mechanizing the Textbook Proof of Huffman’s Algorithm
Proof Pearl: Mechanizing the Textbook Proof of Huffman’s Algorithm
复制标题
Proof Pearl：机械化霍夫曼算法的教科书证明
DOI：
10.1007/s10817-009-9116-y
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Jasmin Christian Blanchette
中科院分区：
文献类型：
--
作者：
Jasmin Christian Blanchette
哈夫曼算法是构建具有最小加权路径长度的二叉树的过程。我们的Isabelle/HOL证明与标准算法教科书中的草图非常相似，揭示了这个过程中的一些障碍。我们形式化的另一个显著特征是使用自定义归纳规则来帮助Isabelle的自动策略，导致对大多数引理的证明非常简短。
Huffman’s algorithm is a procedure for constructing a binary tree with minimum weighted path length. Our Isabelle/HOL proof closely follows the sketches found in standard algorithms textbooks, uncovering a few snags in the process. Another distinguishing feature of our formalization is the use of custom induction rules to help Isabelle’s automatic tactics, leading to very short proofs for most of the lemmas.
在 Isabelle/HOL 中查找终止证明的词典顺序
DOI：
--
发表时间：
2007
期刊：
International Conference on Theorem Proving in Higher Order Logics
影响因子：
--
作者：
Lukas Bulwahn;Alexander Krauss;T. Nipkow
通讯作者：
T. Nipkow
高阶逻辑中的定理证明
DOI：
10.1007/978-3-540-71067-7_8
发表时间：
2008
期刊：
--
影响因子：
--
作者：
Aehlig K
通讯作者：
Aehlig K
伊莎贝尔/HOL 随机测试
DOI：
10.1109/sefm.2004.36
发表时间：
2004
期刊：
Proceedings of the Second International Conference on Software Engineering and Formal Methods, 2004. SEFM 2004.
影响因子：
--
作者：
Stefan Berghofer;T. Nipkow
通讯作者：
T. Nipkow