Dec, 2012

ASP 中超相干性问题的复杂度

PDF
TL;DR本文探讨了如何优化 Answer Set Programming（ASP）系统的 grounding 组件，提出了一种名为 DMS 的变体，适用于具有至少一个答案集的所有 ASP 程序，并证明了在不同情形下正确解决这个问题的复杂度，同时表明了所有相关的 ASP 推理任务都可以转化为超一致程序的任务。
answer set programmingmagic set methodsuper-coherent programscomplexityasp reasoning tasks
发现论文，激发创造
  • 稳定 - 不稳定语义：超越 NP 的普通逻辑程序

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

    Aug, 2016

  • 面向答案集编程中猜测和检查程序的自动集成：元解释器和应用

    本文提出将无环扩展析取逻辑程序转化为分层正向扩展析取逻辑程序的方法并将研究应用于 ASP 中这一强大的工具，扩展了现有策略在编程范式中的应用，进一步提高了处理 NP 问题的方法。

    Jan, 2005

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

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

    Dec, 2018

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

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

    Aug, 2016

  • 一种多引擎的答案集编程方法

    本文提出了一种在现有 ASP 求解器基础之上通过应用机器学习方法，通过识别 ASP 程序的一组易于计算的句法特征，并对这些实例上的性能表现进行归纳学习算法选择策略，从而能够比第三届 ASP 竞赛的任何求解器都更有效地解决实例。

    Jun, 2013

  • 函数的有限可导引理：一次一致性之旅

    通过对逻辑编程领域中的回答集编程（ASP）进行分析，我们提出了一种精细化的方法，描述了 ASP 程序的特征，以及在一些情况下决策问题的半决策解法和用于生成有限扩展的基础步骤。

    May, 2024

  • 超越 NP 问题：量化回答集

    本文提出了一种名为 ASP (Q) 的新语言，引入了程序稳定模型上的量词，进一步拓展了 Answer Set Programming 的建模能力，可以直接对多项式层次中的问题进行建模。

    Jul, 2019

  • 具有命题连接词和聚合运算的逻辑程序

    提出了一种基于命题连词的比喻来定义 aggregates 的方法，可以在 ASP 范式下，对任意命题理论进行扩展，将 aggregates 定义为基础构造，并且结合了表达能力和简洁性。该定义还继承了关于具有嵌套表达式的程序的许多定理，例如强等价性和拆分定理。

    Dec, 2008

  • 利用可能性理论对答案集语义进行特征化和扩展

    本文介绍了新的 Possibilistic ASP (PASP) 模型语义，其中规则被解释为对可能性分布的约束，并且在这些约束的特殊模型中识别为可能主义答案集。此外，我们还发现一种新形式的析取，称为弱析取，其计算复杂性比传统析取容易。

    Nov, 2013

  • 再探可能性答案集编程

    本文介绍了一种基于可能逻辑的新 ASP 模型，称为 Possibilistic answer set programming（PASP）。通过将对 PASP 程序中的规则的确定性附加到每个规则上，我们提出了一种更加合适的 PASP 语义，并且该框架可以轻松使用标准 ASP 求解器实现。

    Mar, 2012