一種具有簡單模型生成功能的仿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