揭示了逻辑程序与基因调控网络的深层联系，解决模型存在性与唯一性问题。
On the Boolean Network Theory of Datalog$^\neg$
- 用布尔网络理论分析逻辑程序依赖结构，通过奇偶环判断模型性质。
- 无奇环时稳定模型存在，无偶环时模型唯一，且数量受反馈顶点集限制。
- 发现最小陷阱空间等价于正则模型，为复杂系统建模提供新视角。
Datalog$^\neg$ 是从演绎数据库到答案集编程等多个领域的重要形式化工具，其模型理论是正常逻辑程序逻辑语义的有限对应，主要基于克拉克闭包及二值或三值规范模型（包括支持、稳定、正则和良基模型）。本文首次建立 Datalog$^\neg$ 与布尔网络理论（最初用于基因调控网络）之间的正式联系。我们证明：在无奇环的 Datalog$^\neg$ 程序中，正则模型与稳定模型等价，从而保证稳定模型的存在性；在无偶环时，稳定部分模型与正则模型具有唯一性。该联系还给出了稳定部分模型、正则模型和稳定模型数量的新上界，其大小由原子依赖图中反馈顶点集的基数决定。此外，该连接引出陷阱空间概念，我们进一步证明：子集最小稳定陷阱空间与正则模型完全等价。
原文摘要 · Abstract (English)
Datalog$^\neg$ is a central formalism used in a variety of domains ranging from deductive databases and abstract argumentation frameworks to answer set programming. Its model theory is the finite counterpart of the logical semantics developed for normal logic programs, mainly based on the notions of Clark's completion and two-valued or three-valued canonical models including supported, stable, regular and well-founded models. In this paper we establish a formal link between Datalog$^\neg$ and Boolean network theory first introduced for gene regulatory networks. We show that in the absence of odd cycles in a Datalog$^\neg$ program, the regular models coincide with the stable models, which entails the existence of stable models, and in the absence of even cycles, we prove the uniqueness of stable partial models and regular models. This connection also gives new upper bounds on the numbers of stable partial, regular, and stable models of a Datalog$^\neg$ program using the cardinality of a feedback vertex set in its atom dependency graph. Interestingly, our connection to Boolean network theory also points us to the notion of trap spaces. In particular we show the equivalence between subset-minimal stable trap spaces and regular models.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。