首页> 外文期刊>Theory and Practice of Logic Programming >D-FLAT: Declarative problem solving using tree decompositions and answer-set programming
【24h】

D-FLAT: Declarative problem solving using tree decompositions and answer-set programming

机译:D-FLAT:使用树分解和答案集编程的声明式问题解决

获取原文
获取原文并翻译 | 示例

摘要

In this work, we propose Answer-Set Programming (ASP) as a tool for rapid prototyping of dynamic programming algorithms based on tree decompositions. In fact, many such algorithms have been designed, but only a few of them found their way into implementation. The main obstacle is the lack of easy-to-use systems which (i) take care of building a tree decomposition and (ii) provide an interface for declarative specifications of dynamic programming algorithms. In this paper, we present D-FLAT, a novel tool that relieves the user of having to handle all the technical details concerned with parsing, tree decomposition, the handling of data structures, etc. Instead, it is only the dynamic programming algorithm itself which has to be specified in the ASP language. D-FLAT employs an ASP solver in order to compute the local solutions in the dynamic programming algorithm. In the paper, we give a few examples illustrating the use of D-FLAT and describe the main features of the system. Moreover, we report experiments which show that ASP-based D-FLAT encodings for some problems outperform monolithic ASP encodings on instances of small treewidth.
机译:在这项工作中,我们提出了答案集编程(ASP)作为基于树分解的动态编程算法快速原型制作的工具。实际上,已经设计了许多这样的算法,但是只有少数算法找到了实现的方法。主要的障碍是缺乏易于使用的系统,该系统(i)负责构建树分解,并且(ii)为动态编程算法的声明性规范提供接口。在本文中,我们介绍了D-FLAT,这是一种新颖的工具,它使用户不必处理与解析,树分解,数据结构的处理等有关的所有技术细节。相反,它只是动态编程算法本身必须使用ASP语言指定。 D-FLAT采用ASP求解器,以便在动态编程算法中计算局部解。在本文中,我们提供了一些示例来说明D-FLAT的用法,并描述了系统的主要功能。此外,我们报告了一些实验,这些实验表明在某些小树宽实例上,基于ASP的D-FLAT编码对某些问题的性能优于单片ASP编码。

著录项

  • 来源
    《Theory and Practice of Logic Programming》 |2012年第5期|p.445-464|共20页
  • 作者单位

    Institute of Information Systems 184/2 Vienna University of Technology Favoritenstrasse 9-11, 1040 Vienna, Austria;

    Institute of Information Systems 184/2 Vienna University of Technology Favoritenstrasse 9-11, 1040 Vienna, Austria;

    Institute of Information Systems 184/2 Vienna University of Technology Favoritenstrasse 9-11, 1040 Vienna, Austria;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号