揭示克罗姆逻辑程序的代数结构及其与自动机的联系。
The algebra of Krom logic programs
- 用序列复合构建克罗姆程序的独异点结构。
- 给出生成集与规范分解，刻画克罗姆星号与ω运算。
- 适合逻辑编程与代数自动机研究者阅读。
本文研究仅含事实和最多一个体原子的规则的克罗姆逻辑程序的代数结构。证明序列复合使克罗姆程序类自然形成一个独异点，并可扩展为克罗姆半环、克罗姆准环、克罗姆-康韦半环及克罗姆-康韦ω半环。进一步给出显式生成集与规范分解，研究相关的${}^ω$-算子，以图论术语刻画克莱尼星号，并将有限克罗姆独异点与变换独异点及有限状态自动机相联系。这些结果建立了逻辑程序设计、代数自动机理论与代数图论之间的新关联。
原文摘要 · Abstract (English)
This paper investigates the algebraic structure of Krom logic programs, consisting only of facts and rules with at most one body atom. We show that sequential composition endows the class of Krom programs with a natural monoid structure and that this structure admits rich algebraic extensions to Krom seminearrings, Krom quemirings, Krom-Conway seminearrings, and Krom-Conway omegaseminearrings. Furthermore, we establish explicit generating sets and canonical decompositions, study the associated ${}^ω$-operator, characterize the Kleene star in graph-theoretic terms, and relate finite Krom monoids to transformation monoids and finite-state automata. These results provide new connections between logic programming, algebraic automata theory, and algebraic graph theory.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。