一种具有简单模型生成功能的仿ASP语言

• 2019 年 12 月 29 日
• 筆記

原文题目: A Paraconsistent ASP-like Language with Tractable Model Generation

摘要： 回答集编程（ASP）是当今基于规则的主要知识表示工具。虽然现有的ASP变体具有高效的实现，但是生成一个回答集仍然是棘手的。本研究的目标是定义一种新的类似asp的规则语言4SP，它具有可处理的模型生成功能。该语言结合了ASP和次协调规则语言4QL的思想。虽然4SP共享了ASP的语法，而对于每个程序，所有的答案集都在4SP模型中，新语言在逻辑基础上不同于ASP，其使用的方法和计算模型的复杂性。

正如我们在文章中所展示的，4QL可以被看作是ASP程序的一个准一致的副本，相对于默认否定，它是分层的。尽管为4QL程序生成受良好支持的模型是容易的，但是减少分层使4QL和ASP都变得难以处理。为了在允许非分层程序的同时保持可处理性，在4SP中，我们引入了将程序与缺省否定的真值假设交织在一起的试验表达式。这使得我们能够开发具有确定性多项式时间复杂度的模型生成算法。

我们还展示了4SP、ASP和4QL之间的关系。

原文作者：Andrzej Szalas

原文地址：https://arxiv.org/abs/1912.09715