通过依赖图分析逻辑程序的正则模型存在性与唯一性。
Graphical Conditions for the Existence, Unicity and Number of Regular Models
- 基于依赖图的结构条件判断正则模型是否存在
- 给出正则模型唯一性的充分条件，推广了已有结果
- 首次提供正则模型数量的上界，适用于有向环结构
正则模型是有限基正常逻辑程序的一种特殊部分（三值）模型，对应于不确定度最小的稳定部分模型。本文研究有限基正常逻辑程序依赖图上的图形条件，以分析其正则模型的存在性、唯一性和数量。主要成果包括：1）非平凡（即非二值）正则模型存在的必要条件；2）正则模型唯一性的充分条件；3）基于正反馈顶点集的两个正则模型数量上界。前两项推广了You和Yuan（1994）针对具有良基分层的正常逻辑程序所得的有限情形结果；第三项为本文新发现。证明的关键在于建立有限基正常逻辑程序与布尔网络理论之间的联系。
原文摘要 · Abstract (English)
The regular models of a normal logic program are a particular type of partial (i.e. 3-valued) models which correspond to stable partial models with minimal undefinedness. In this paper, we explore graphical conditions on the dependency graph of a finite ground normal logic program to analyze the existence, unicity and number of regular models for the program. We show three main results: 1) a necessary condition for the existence of non-trivial (i.e. non-2-valued) regular models, 2) a sufficient condition for the unicity of regular models, and 3) two upper bounds for the number of regular models based on positive feedback vertex sets. The first two conditions generalize the finite cases of the two existing results obtained by You and Yuan (1994) for normal logic programs with well-founded stratification. The third result is also new to the best of our knowledge. Key to our proofs is a connection that we establish between finite ground normal logic programs and Boolean network theory.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。