• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'01), Sep 5-7, 2001, Florence, Italy >Development Reuse and the Logic Program Derivation of Two String-Matching Algorithms
【24h】

Development Reuse and the Logic Program Derivation of Two String-Matching Algorithms

机译：两种字符串匹配算法的开发重用和逻辑程序推导

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Program transformation advocates the development of programs by applying a sequence of meaning-preserving rules to a specification, thereby obtaining an implementation. The cost of program development and maintenance decreases if previous, similar derivations can be reused conveniently. Through the string-matching problem, we study the reuse of complete parts of the derivation of an algorithm, in the derivation of another, "similar" algorithm. In particular, we first derive the search stage of a variant of the Boyer-Moore algorithm, and then reuse some "developments" in a derivation of the search stage of the Knuth-Morris-Pratt algorithm. Several advantages result from employing logic programming. First, we get the semantic benefit of having a logical basis. Second, we can easily exploit nondeterminism. Third, we link both derivations by observing that repetitive "deterministic" unfolding (i.e. sequences of unfolding steps that halt when more than one clause would be inferred) is closely related to the preprocessing stage of both algorithms.
机译：程序转换通过将一系列保留含义的规则应用于规范来提倡程序的开发，从而获得实现。如果可以方便地重用以前的类似衍生程序，则程序开发和维护的成本会降低。通过字符串匹配问题，我们研究了另一种“相似”算法的推导中算法的完整部分的重用。特别地，我们首先导出Boyer-Moore算法的变体的搜索阶段，然后在Knuth-Morris-Pratt算法的搜索阶段的推导中重用一些“发展”。采用逻辑编程可带来许多优势。首先，我们从逻辑上获得了语义上的好处。其次，我们可以轻松利用不确定性。第三，我们通过观察重复的“确定性”展开（即，当推断出多个子句时停止的展开步骤序列）与两种算法的预处理阶段密切相关，将这两种推导联系起来。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号