• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Logic for Programming, Artificial Intelligence, and Reasoning(LPAR 2005); 20051202-06; Montego Bay(JM) >An Algorithmic Account of Ehrenfeucht Games on Labeled Successor Structures
【24h】

An Algorithmic Account of Ehrenfeucht Games on Labeled Successor Structures

机译：标记后继结构上的Ehrenfeucht游戏的算法说明

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

摘要

Ehrenfeucht-Fraiesse games are commonly used as a method to measure the expressive power of a logic, but they are also a flexible tool to compare structures. To exploit such a comparison power, explicit conditions characterizing the winning strategies for both players must be provided. We give a necessary and sufficient condition for Duplicator to win games played on finite structures with a successor relation and a finite number of unary predicates. This structural characterization suggests an algorithmic approach to the analysis of games, which can be used to compute the "remoteness" of a game and to determine the optimal moves for both players, that is, to derive algorithms for Spoiler and Duplicator that play optimally. We argue that such an algorithmic solution may be used in contexts where the "degree of similarity" between two structures must be measured, such as the comparison of biological sequences.
机译：Ehrenfeucht-Fraiesse游戏通常用作衡量逻辑表达能力的方法，但它们也是比较结构的灵活工具。为了利用这种比较能力，必须提供明确的条件来表征两个玩家的获胜策略。我们为复制器赢得具有后继关系和有限数量的一元谓词的有限结构上的游戏赢得胜利提供了充要条件。这种结构特征提出了一种用于游戏分析的算法方法，该方法可用于计算游戏的“远程性”并确定两个玩家的最佳移动方式，也就是派生出最佳玩法的剧透和复制者算法。我们认为这种算法解决方案可用于必须测量两个结构之间的“相似程度”的环境中，例如生物序列的比较。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号