Jan, 2023

逻辑程序结构硬度的表征：为什么对于树宽而言，环和可达性很难？

PDF
TL;DR本文介绍了一种从 SAT 到 normal ASP 的新型减少方法，并通过建立依赖图的循环长度（SCC 大小）与树宽之间所需的功能依赖性，以一种细粒度的方式刻画了硬度。
answer set programmingcomputational complexitytreewidthnormal aspsat
发现论文，激发创造
  • 基于树宽的 ASP 到 SAT 的归约 -- ASP 普通形式难度比 SAT 高吗？

    本文提出了一种新的从 ASP 到 SAT 的规约（Reduction）方法，并证明了在考虑 Treewidth 时，一般 ASP 的难度比 SAT 稍微更高，同时还对新规约进行了实证研究。

    Oct, 2022

  • 关于回答集编程的结构难度的延伸版本：结构能否有效地限制析取的能力？

    Answer Set Programming (ASP) 是一个以知识表示为重点的问题建模和求解框架，在工业应用方面有着快速增长。这篇论文通过对结构参数的分类研究了 disjunctive ASP 的复杂性，提供了多个重要参数的双指数下界，并指出除了 vertex cover size 之外的选项是有限的。

    Feb, 2024

  • 关于 Answer-Set 编程的 Clique-Width 与有向宽度测量

    本文研究了绝对性集合编程中的困难问题，并提出了一种新的动态规划算法来解决一个图形参数问题，即带符号的团宽度（signed clique-width）

    Jun, 2016

  • 基于启发式分解的答案集计算优化

    该研究提出了一种新的优化方法，基于树分解技术和启发式算法，可以将一个输入的逻辑程序转化为一个等价的程序以提高 ASP 系统的求解效率，并在实验中验证了其有效性。

    Dec, 2018

  • 有界基础的答案集编程

    本文提出了基于边界约束的 ASP（Bound Founded Answer Set Programming）方法，解决了 ASP 系统中存在的基于有限域变量建模的算法性难题，同时将 ASP 的语义从布尔值和常规规则扩展到了数值变量上。

    May, 2014

  • 非基础规则在答案集编程中的威力

    该论文提出了一种新的 ASP 编码模式，通过利用实际问题的大规则来编码难题，尤其针对 NP 问题能提供更强的表达能力，并且提供基于规则分解技术的解决方案，初步的基准测试表明，放弃固定程序的简便方式可以显著提高速度。

    Aug, 2016

  • 可行的答案集编程后门

    本文介绍了如何使用 backdoors 的概念来识别能够使 ASP 问题可行的新限制，展示了 backdoors 如何作为一个统一的框架，能够容纳文献中已知的几个可行限制，并展示了如何利用 backdoors 将参数化复杂性理论的最新算法结果应用到答案集编程领域。

    Apr, 2011

  • 利用树宽度进行认识逻辑程序的数量推理

    本篇论文介绍了一种利用图形方法和动态规划结合已有的搜索求解器来解决定量推理问题的新系统，可以有效地处理 Answer Set Programming 方法中 epistemic logic programs 的复杂问题。

    Aug, 2021

  • 稳定 - 不稳定语义：超越 NP 的普通逻辑程序

    提出一种基于逻辑编程的建模范式，将 ASP 和 QBF 的最佳特性相结合，实现对高层次搜索问题的编码。

    Aug, 2016

  • 非安全底部 ASP 程序的调试：技术和图形化工具

    提出了一种新的 ASP 程序调试方法，该方法基于非基础程序中所涉及的非基础规则，通过问答能够精确定位程序中的错误。这种调试器集成在 ASPIDE 中，使用 WASP 进行实现。

    Aug, 2018