摘要翻译:
析取有限程序是一类允许函数符号从而允许无限域的逻辑程序。它们具有很好的计算特性,例如,地面查询是可判定的,而在一般情况下,稳定模型语义是高度不可判定的。本文证明了在稳定模型语义下,一类更大的有限递归程序保留了有限程序的大部分优良性质,即:(一)有限递归程序具有紧性;(ii)不一致性检验和怀疑推理是半可信的;(iii)对于正规有限递归程序,怀疑解析是完全的。此外,我们展示了如何使用有限子集的地面程序实例化来检查不一致性和回答怀疑的查询。通过推广Lifschitz和Turner的分裂序列定理,我们证明了如果输入程序P是有限递归的,则由任意光滑分裂欧米伽序列确定的部分稳定模型收敛于P的稳定模型。
---
英文标题:
《On finitely recursive programs》
---
作者:
Sabrina Baselice, Piero A. Bonatti, Giovanni Criscuolo
---
最新提交年份:
2009
---
分类信息:
一级分类:Computer Science 计算机科学
二级分类:Artificial Intelligence 人工智能
分类描述:Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域,除了视觉、机器人、机器学习、多智能体系统以及计算和语言(自然语言处理),这些领域有独立的学科领域。特别地,包括专家系统,定理证明(尽管这可能与计算机科学中的逻辑重叠),知识表示,规划,和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
一级分类:Computer Science 计算机科学
二级分类:Logic in Computer Science 计算机科学中的逻辑
分类描述:Covers all aspects of logic in computer science, including finite model theory, logics of programs, modal logic, and program verification. Programming language semantics should have Programming Languages as the primary subject area. Roughly includes material in ACM Subject Classes D.2.4, F.3.1, F.4.0, F.4.1, and F.4.2; some material in F.4.3 (formal languages) may also be appropriate here, although Computational Complexity is typically the more appropriate subject area.
涵盖计算机科学中逻辑的所有方面,包括有限模型理论,程序逻辑,模态逻辑和程序验证。程序设计语言语义学应该把程序设计语言作为主要的学科领域。大致包括ACM学科类D.2.4、F.3.1、F.4.0、F.4.1和F.4.2中的材料;F.4.3(形式语言)中的一些材料在这里也可能是合适的,尽管计算复杂性通常是更合适的主题领域。
--
---
英文摘要:
Disjunctive finitary programs are a class of logic programs admitting function symbols and hence infinite domains. They have very good computational properties, for example ground queries are decidable while in the general case the stable model semantics is highly undecidable. In this paper we prove that a larger class of programs, called finitely recursive programs, preserves most of the good properties of finitary programs under the stable model semantics, namely: (i) finitely recursive programs enjoy a compactness property; (ii) inconsistency checking and skeptical reasoning are semidecidable; (iii) skeptical resolution is complete for normal finitely recursive programs. Moreover, we show how to check inconsistency and answer skeptical queries using finite subsets of the ground program instantiation. We achieve this by extending the splitting sequence theorem by Lifschitz and Turner: We prove that if the input program P is finitely recursive, then the partial stable models determined by any smooth splitting omega-sequence converge to a stable model of P.
---
PDF链接:
https://arxiv.org/pdf/0901.2850