Paper deep dive
The algebra of Krom logic programs
Christian Antić
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 97%
Last extracted: 6/20/2026, 6:46:59 AM
Summary
This paper investigates the algebraic structure of Krom logic programs, which consist of facts and rules with at most one body atom. The author demonstrates that sequential composition endows these programs with a natural monoid structure, extending into a hierarchy of algebraic structures including Krom seminearrings, Krom quemirings, and Krom-Conway seminearrings/omegaseminearrings. The research establishes connections between logic programming and algebraic automata theory, specifically showing that the Kleene star represents graph reachability and the omega-operator ($\omega$) captures the least model semantics ($LM(K)$).
Entities (9)
Relation Signals (4)
omega-operator → captures → least model semantics
confidence 100% · the $\omega$-operator captures the least model semantics of Krom programs.
Krom logic programs → hasalgebraicstructure → Krom seminearring
confidence 100% · 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 logic programs → isrelatedto → algebraic automata theory
confidence 100% · These results provide new connections between logic programming, algebraic automata theory, and algebraic graph theory.
Kleene star → represents → graph reachability
confidence 100% · characterize the Kleene star in graph-theoretic terms... Kleene star captures graph reachability.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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 ${}^\omega$-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.
Tags
Links
- Source: https://arxiv.org/abs/2606.15719v1
- Canonical: https://arxiv.org/abs/2606.15719v1
Trouble viewing inline? Open PDF directly →
Full Text
43,906 characters extracted from source content.
Expand or collapse full text
The algebra of Krom logic programs Christian Antić christian.antic@icloud.com Vienna University of Technology Vienna, Austria Abstract. 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. Keywords: monoids, seminearrings, quemirings, Conway semirings, sequential composition, least models, transformation monoids, finite-state automata, algebraic logic programming. Contents 1 Introduction 2 Preliminaries 3 The proper rule operator 3.1 Basic properties 3.2 Krom quemirings 4 The facts operator 5 Krom-Conway seminearrings 6 Krom-Conway omegaseminearrings 6.1 Omega and composition 6.2 Omega and set union 7 Permutation programs 8 Generators and canonical decompositions 9 Automata 10 Conclusion References 1. Introduction Logic programs constitute one of the most extensively studied rule-based formalisms in theoretical computer science and mathematical logic (cf. [6, 14]). Among them, Horn theories occupy a particularly prominent position due to their favorable computational and logical properties and their numerous applications in computer science [15]. The sequential composition of propositional logic programs was introduced in [3, 4] and subsequently extended to answer set programming in [2]. This operation endows logic programs with an algebraic structure that has so far received comparatively little attention. More broadly, this work is part of an ongoing effort to develop an algebraic theory of logic programming, in which logic programs are studied as algebraic objects equipped with natural operations and identities. From this perspective, sequential composition plays a role analogous to multiplication in semiring theory and provides a foundation for investigating structural decomposition, generation, and transformation of logic programs. The Krom fragment [13] occupies a distinguished position within this program. On the one hand, it is expressive enough to exhibit non-trivial algebraic phenomena, including natural connections with graph theory, permutation groups, and automata. On the other hand, it enjoys structural properties that fail for general logic programs, such as the compatibility of sequential composition with set union and the proper rule operator. Moreover, Krom programs arise as canonical building blocks in decomposition results for Horn programs [5]. These observations suggest that the Krom fragment provides a natural starting point for the development of an algebraic theory of logic programming. The main objective of this paper is to identify and study the algebraic structures naturally induced by sequential composition on Krom logic programs. We show that this seemingly elementary fragment supports a surprisingly rich hierarchy of algebraic structures, including monoids, quemirings, Conway seminearrings, and omegaseminearrings, and admits close connections with graph theory, transformation monoids, and automata. Besides being of independent interest, Krom programs arise naturally as the basic building blocks in the algebraic theory of set-like operations on logic programs [5, Minimalist Decomposition Theorem]. In particular, every minimalist111A propositional Horn program is called minimalist in [5] if it contains at most one rule for each rule head. propositional Horn program admits a canonical decomposition into Krom components, providing further motivation for studying their algebraic properties. A characteristic feature of the Krom fragment is that sequential composition distributes over union from the left, a property that fails for arbitrary propositional logic programs (cf. [3, Example 8]). Furthermore, the proper rule operator, which extracts the non-factual rules of a program, is an endomorphism with respect to sequential composition. These observations make the Krom fragment particularly amenable to an algebraic treatment. The main contribution of this paper is the development of an algebraic theory of Krom logic programs under sequential composition. We show that the resulting structures naturally give rise to monoids, seminearrings, quemirings, Conway seminearrings, and Conway omegaseminearrings, thereby revealing close connections with semiring-based algebraic automata theory [11] and algebraic graph theory [12]. In particular, sequential composition corresponds to relational composition, while the Kleene star captures graph reachability. In a broader sense, this paper constitutes another step towards an algebraic theory of logic programming, a research direction initiated by Richard O’Keefe [16] and subsequently pursued in the context of modular logic programming (see, e.g., [7, 8]) as well as in the author’s recent work [1, 2, 3, 4, 5]. 2. Preliminaries In this section, we recall the syntax, semantics, and composition of (possibly infinite) propositional Krom222The Krom fragment is named after the author of [13]. logic programs, consisting only of rules with at most a single body atom, by following the lines of [3]. Let A be an alphabet of propositional atoms. A (propositional Krom logic) program over A is a set of (Krom) rules of two forms, (i) facts of the form a∈Aa∈ A, and (i) proper rules of the form a←ba← b, for a,b∈Aa,b∈ A. We denote the set of all Krom programs over A by AK_A or simply by K in case A is understood from the context. We denote the facts and proper rules in K by f(K)f(K) and p(K)p(K), respectively. An interpretation is any subset of A. We define the entailment relation, for every interpretation I, inductively as follows: (1) for an atom a, I⊧aI a if a∈Ia∈ I; (2) for a proper rule, I⊧a←bI a← b if I⊧bI b implies I⊧aI a; (3) for a propositional Krom program K, I⊧KI K if I⊧rI r holds for each rule r∈Kr∈ K. In case I⊧KI K, we call I a model of K. The set of all models of K has a least element with respect to set inclusion called the least model of K and denoted by LM(K)LM(K). We shall now recall the sequential composition [3] of Krom programs. In the rest of the paper, K and L denote Krom programs over some fixed alphabet A. Define the (sequential) composition of K and L by K∘L:=f(K)∪a∈A∣a←b∈K,b∈L∪a←b∣a←c∈K,c←b∈L. K L:=f(K)∪\a∈ A a← b∈ K,\;b∈ L\∪\a← b a← c∈ K,\;c← b∈ L\. We simply write KLKL in case the composition operation is understood. We define the unit program over A by 1A:=a←a∣a∈A. 1_A:=\a← a a∈ A\. As usual, we often omit A and write 11. Interpretations are left zeros, that is, (1) IK=I IK=I holds for every Krom program K and interpretation I. We have the following structural result: Theorem 1. [3, Thm. 12] The structure (,∪,∘,∅,1)(K,∪, , ,1) forms a seminearring [18] (and almost333The inequality K∅≠∅K ≠ is the only reason why the set of all Krom programs (possibly containing facts) fails to be a semiring; but see Theorem 4. a semiring) as it satisfies the following identities, for all Krom programs K,L,M∈K,L,M : (2) (K∪L)∪M (K∪ L)∪ M =K∪(L∪M) =K∪(L∪ M) (3) K∪L K∪ L =L∪K =L∪ K (4) ∅∪K ∪ K =K∪∅=K =K∪ =K (5) K(LM) K(LM) =(KL)M =(KL)M (6) K1 K1 =1K=K =1K=K (7) M(K∪L) M(K∪ L) =KK∪ML =K∪ ML (8) (L∪M)K (L∪ M)K =KM∪LK =KM∪ LK (9) ∅K K =∅. = . From now on, we call (,∪,∘,∅,1)(K,∪, , ,1) the Krom seminearring. 3. The proper rule operator In this section, we investigate the proper rule operator p, which extracts the proper rules of a Krom program by removing all facts. Besides serving as a basic structural decomposition, the operator p exhibits remarkable algebraic properties with respect to sequential composition and set union. In particular, it gives rise to a natural quemiring structure on finite Krom seminearrings, thereby revealing an unexpected connection between Krom programs and algebraic structures originating in automata theory. 3.1. Basic properties We begin by collecting the fundamental algebraic properties of the proper rule operator. In particular, we show that p is compatible with the basic operations on Krom programs and therefore behaves as a natural algebraic projection onto the proper part of a program. These identities will serve as the foundation for the richer structures developed in the subsequent subsection. Theorem 2. The proper rule operator p is an endomorphism of the Krom seminearring (,∪,∘,∅,1)(K,∪, , ,1) thus satisfying (10) p(K∪L) p(K∪ L) =p(K)∪p(L), =p(K)∪ p(L), (11) p(KL) p(KL) =p(K)p(L), =p(K)p(L), (12) p(1) p(1) =1, =1, (13) p(∅) p( ) =∅, = , for all Krom programs K and L. Proof. An immediate consequence from the definitions. ∎ Remark 3. A distinguishing feature of the Krom fragment is that the proper rule operator commutes with sequential composition. In contrast, this identity does not hold for arbitrary propositional logic programs; see [3, §4.4]. Theorem 4. The Krom algebra (p(),∪,∘,∅,1)(p(K),∪, , ,1) containing only proper Krom programs is an idempotent semiring. Proof. For every proper Krom program K∈p()K∈ p(K), we have K∅=∅. K = . Hence the right annihilation axiom holds on p()p(K), so together with Theorem 1 all semiring axioms are satisfied. ∎ Thus, removing all facts restores the missing right-annihilation property and turns the Krom seminearring into a semiring. 3.2. Krom quemirings Quemirings were introduced in [10] in the context of algebraic automata theory (see e.g. [11, p.110]). The following theorem shows that they also arise naturally in the algebra of Krom logic programs: Theorem 5. The Krom algebra (,∪,∘,∅,1,p)(K,∪, , ,1,p) forms a quemiring, henceforth called the Krom quemiring. Explicitly, for all K,L,M∈K,L,M , the following identities hold in addition to the identities in Theorem 1: p(K)(L∪M) p(K)(L∪ M) =(p(K)L)∪(p(K)M), =(p(K)L)∪(p(K)M), K K =p(K)∪(K∅), =p(K)∪(K ), p(K)∅ p(K) =∅, = , p(K∪L) p(K∪ L) =p(K)∪p(L), =p(K)∪ p(L), p(KL) p(KL) =p(K)p(L). =p(K)p(L). Proof. The first identity holds by distributivity (7). The second and third identities follow from the fact that K∅=14f(K)K eq:f(K)=K0=f(K). The last two identities hold trivially. ∎ 4. The facts operator This section studies elementary algebraic properties of the facts operator f, which extracts the facts of a Krom program. Our first observation is that the facts operator can be reduced to composition via (14) f(K)=K∅. f(K)=K . This means that we can extract the facts of a Krom program K by composing it with the empty program. The next result summarizes the interaction of the facts operator with set union and intersection: Proposition 6. The facts operator is a homomorphism of bounded lattices f:(A,∪,∩,∅,FA)→(A,∪,∩,∅,A),f:(K_A,∪,∩, ,F_A)→(I_A,∪,∩, ,A), where FAF_A denotes the Krom program containing all Krom rules over A. In other words, (15) f(K∪L) f(K∪ L) =f(K)∪f(L) =f(K)∪ f(L) (16) f(K∩L) f(K∩ L) =f(K)∩f(L) =f(K)∩ f(L) (17) f(∅) f( ) =∅ = (18) f(FA) f(F_A) =A. =A. We now want to study the interaction between the facts operator and composition. The facts of the composition KLKL can be computed as (19) f(KL) f(KL) =f(K)∪p(K)f(L), =f(K)∪ p(K)f(L), where p(K)p(K) denotes the proper rules in K. More generally, the next result provides a concise formula for the computation of the facts of a sequence of program compositions which will often be used below: Theorem 7. We can compute the facts of the sequential composition of the Krom programs K1,…,KnK_1,…,K_n, n≥1n≥ 1, by (20) f(K1…Kn)=f(K1)∪⋃i=1n−1(p(K1…Ki)f(Ki+1)). f(K_1… K_n)=f(K_1)∪ _i=1^n-1(p(K_1… K_i)f(K_i+1)). Proof. By induction on n. The induction base n=1n=1 holds trivially. For the induction step, we compute f(K1…Kn+1) f(K_1… K_n+1) =19f(K1)∪p(K1)f(K2…Kn+1) eq:f(KL)=f(K_1)∪ p(K_1)f(K_2… K_n+1) =IHf(K1)∪p(K1)(f(K2)∪⋃i=2n(p(K2…Ki)f(Ki+1))) IH=f(K_1)∪ p(K_1) (f(K_2)∪ _i=2^n(p(K_2… K_i)f(K_i+1)) ) =7f(K1)∪p(K1)f(K2)∪⋃i=2n(p(K1)p(K2…Ki)f(Ki+1)) eq:M(K_cup_L)=f(K_1)∪ p(K_1)f(K_2)∪ _i=2^n(p(K_1)p(K_2… K_i)f(K_i+1)) =11f(K1)∪p(K1)f(K2)∪⋃i=2n(p(K1K2…Ki)f(Ki+1)) eq:p(KL)=f(K_1)∪ p(K_1)f(K_2)∪ _i=2^n(p(K_1K_2… K_i)f(K_i+1)) =f(K1)∪⋃i=1n(p(K1…Ki)f(Ki+1)). =f(K_1)∪ _i=1^n(p(K_1… K_i)f(K_i+1)). ∎ 5. Krom-Conway seminearrings Krom programs can naturally be viewed as directed graphs with designated vertices, with sequential composition corresponding to relational composition and the Kleene star corresponding to reachability. More precisely, every proper Krom program K over an alphabet A can be identified with the directed graph whose vertex set is A and whose edge set consists of all pairs (b,a)(b,a) such that the rule a←ba← b belongs to K. Under this correspondence, sequential composition coincides with relational composition of directed graphs. This interpretation motivates the introduction of the Kleene star and Kleene plus on proper Krom programs. For every proper Krom program K, we define K∗:=⋃n≥0KnandK+:=KK∗.K := _n≥ 0K^n K^+:=K . Intuitively, K∗K contains precisely those rules a←ba← b for which there exists a directed path from b to a in the graph represented by the proper rules of K. Thus, K∗K can be viewed as the reflexive transitive closure of K and provides an algebraic characterization of reachability. We now investigate the interaction of the Kleene star with the remaining algebraic operations. Proposition 8. For any Krom program K and interpretation I, (21) K∪I=I∗K. K∪ I=I K. Proof. The Kleene star acts on interpretations as (22) I∗=1∪I. I =1∪ I. This yields K∪I=1K∪IK=8(1∪I)K=22I∗K. K∪ I eq:IK=I=K∪ IK eq:(K_cup_L)M=(1∪ I)K eq:I^ast=I K. ∎ Proposition 9. The Kleene star and the proper rule operator p are compatible in the sense that (23) p(K∗)=p(K)∗ p(K )=p(K) holds for every Krom program K. Proof. p(K∗)=p(⋃n≥0Kn)=10⋃n≥0p(Kn)=11⋃n≥0p(K)n=p(K)∗. p(K )=p( _n≥ 0K^n) eq:p(K_cup_L)= _n≥ 0p(K^n) eq:p(KL)= _n≥ 0p(K)^n=p(K) . ∎ In the algebraic theory of formal languages and automata (see, e.g., [11]), the so-called Conway axioms, introduced by J. H. Conway in [9], play a fundamental role. We briefly recall two of them here. Let (S,+,⋅,0,1,)∗(S,+,·,0,1, ) be a starsemiring in the sense of [11], that is, a semiring (S,+,⋅,0,1)(S,+,·,0,1) enriched with an unary star operation ∗. Two equations from [9, p.15] will be important for our purposes (see also [11, p.15]): • The sum-star equation (a+b)∗=(a∗b)∗a∗ (a+b) =(a b) a for all a,b∈Sa,b∈ S. • The product-star equation (ab)∗=1+a(ba)∗b (ab) =1+a(ba) b for all a,b∈Sa,b∈ S. Conway identities provide an algebraic axiomatization of Kleene star and play a central role in the theory of regular languages and automata. It is therefore natural to ask whether the Kleene star arising from Krom programs satisfies these identities. There is a natural analogy between formal languages and Krom programs, and more generally between starsemirings and starseminearrings. This motivates the following definition: Definition 10. A Conway seminearring is a seminearring enriched with a star operation satisfying the sum-star equation and the product-star equation. Theorem 11. The Krom seminearring together with the Kleene star operation is a Conway seminearring, henceforth called the Krom-Conway seminearring. Explicitly, in addition to the axioms in Theorem 1 we have (24) (K∪L)∗ (K∪ L) =(K∗L)∗K∗ =(K L) K (25) (KL)∗ (KL) =1∪K(LK)∗L. =1∪ K(LK) L. Proof. We first prove the sum-star-equation. Every word over the alphabet K,L\K,L\ can be written uniquely in the form Ki1LKi2L⋯KimLKim+1, K^i_1LK^i_2L·s K^i_mLK^i_m+1, where m≥0m≥ 0 and i1,…,im+1≥0i_1,…,i_m+1≥ 0. Hence (K∪L)∗=⋃m≥0⋃i1,…,im+1≥0Ki1LKi2L⋯KimLKim+1=⋃m≥0(K∗L)mK∗=(K∗L)∗K∗. (K∪ L) = _m≥ 0 _i_1,…,i_m+1≥ 0K^i_1LK^i_2L·s K^i_mLK^i_m+1= _m≥ 0(K L)^mK =(K L) K . We now prove the product-star-equation. We compute (KL)∗=⋃n≥0(KL)n=1∪⋃n≥1(KL)n=1∪⋃n≥1K(LK)n−1L=1∪K(⋃m≥0(LK)m)L=1∪K(LK)∗L. (KL) = _n≥ 0(KL)^n=1∪ _n≥ 1(KL)^n=1∪ _n≥ 1K(LK)^n-1L=1∪ K ( _m≥ 0(LK)^m )L=1∪ K(LK) L. ∎ Theorem 12. The starsemiring of proper Krom programs is a Conway semiring. Proof. Analogous to the proof of Theorem 11. ∎ Corollary 13. For any Krom program K and interpretation I, (26) (K∪I)∗=K∗∪K∗I. (K∪ I) =K ∪ K I. Proof. We have (K∪I)∗=24(K∗I)∗K∗=(⋃n≥0(K∗I)n)K∗. (K∪ I) eq:(K_cup_L)^ast=(K I) K = ( _n≥ 0(K I)^n )K . Now since, for every n≥1n≥ 1, (27) (K∗I)n=K∗IK∗I…K∗I=1K∗I, (K I)^n=K IK I… K I eq:IK=I=K I, we can simplify the above expression to (⋃n≥0(K∗I)n)K∗=27(1∪K∗I)K∗=8K∗∪K∗IK∗=1K∗∪K∗I. ( _n≥ 0(K I)^n )K eq:(K^astI)^n=(1∪ K I)K eq:(K_cup_L)M=K ∪ K IK eq:IK=I=K ∪ K I. ∎ 6. Krom-Conway omegaseminearrings We follow the algebraic tradition of semiring-based automata theory [11] and study a seminearring equipped with an additional unary omega operation. In the rest of the paper, we will be concerned with the Krom algebra A:=(A,∪,∘,∅,1A,,∗)ω K_A:=(K_A,∪, , ,1_A, ,^ω) of Krom programs under set union and composition together with the Kleene star and the least model ω-operation defined as Kω:=⋃n≥1(Kn∅), K^ω:= _n≥ 1(K^n ), henceforth called the Krom-Conway omegaseminearring over A. The next result provides an explicit characterization of the ω-operator. It shows that the least model of a Krom program is obtained by repeatedly propagating its facts through its proper part. Theorem 14. For any Krom program K, we have (28) Kω=p(K)∗f(K). K^ω=p(K) f(K). Proof. Kω K^ω =⋃n≥1(Kn∅) = _n≥ 1(K^n ) =14⋃n≥1f(Kn) eq:f(K)=K0= _n≥ 1f(K^n) =20⋃n≥1(f(K)∪⋃i=1n−1(p(Ki)f(K))) eq:f(K1-Kn)= _n≥ 1 (f(K)∪ _i=1^n-1(p(K^i)f(K)) ) =11f(K)∪⋃n≥1⋃i=1n−1(p(K)if(K)) eq:p(KL)=f(K)∪ _n≥ 1 _i=1^n-1(p(K)^if(K)) =f(K)∪⋃n≥1(p(K)nf(K)) =f(K)∪ _n≥ 1(p(K)^nf(K)) =⋃n≥0(p(K)nf(K)) = _n≥ 0(p(K)^nf(K)) =(⋃n≥0p(K)n)f(K) = ( _n≥ 0p(K)^n )f(K) =p(K)∗f(K). =p(K) f(K). ∎ Proposition 15. For every Krom program K, (29) Kω=f(K∗). K^ω=f(K ). Proof. We compute f(K∗) f(K ) =f(⋃n≥0Kn) =f( _n≥ 0K^n) =15⋃n≥0f(Kn) eq:f(K_cup_L)= _n≥ 0f(K^n) =20⋃n≥0(f(K)∪⋃i=1n−1p(K)if(K)) eq:f(K1-Kn)= _n≥ 0 (f(K)∪ _i=1^n-1p(K)^if(K) ) =f(K)∪⋃n≥0⋃i=1n−1p(K)if(K) =f(K)∪ _n≥ 0 _i=1^n-1p(K)^if(K) =f(K)∪⋃n≥1p(K)nf(K) =f(K)∪ _n≥ 1p(K)^nf(K) =8f(K)∪(⋃n≥1p(K)n)f(K) eq:(K_cup_L)M=f(K)∪ ( _n≥ 1p(K)^n )f(K) =f(K)∪p(K)+f(K) =f(K)∪ p(K)^+f(K) =p(K)∗f(K) =p(K) f(K) =28Kω. eq:K^omega=K^ω. ∎ Corollary 16. For any Krom program K, Kω⊆K∗ K^ω K Proof. A direct consequence of (29). ∎ Corollary 17. The ω-operator is compatible with Kleene star in the in the sense that (K∗)ω=(Kω)+ (K )^ω=(K^ω)^+ holds for every Krom program K. Proof. We have (K∗)ω=29f((K∗)∗)=f(K∗)=Kω=(Kω)+, (K )^ω eq:f(K^ast)=f((K ) )=f(K )=K^ω=(K^ω)^+, where the second identity follows from the idempotency of the Kleene star and the last identity follows from the fact that Kleene plus is the identity on interpretations. ∎ We are now in the position to prove that the ω-operator captures the least-model semantics of Krom programs; cf. [3, Thm. 40]. Theorem 18. For every Krom program K, we have Kω=LM(K).K^ω=LM(K). Proof. Recall the van Emden-Kowalski immediate consequence operator [17] TK(I):=a∈A∣a←B∈K,B⊆I.T_K(I):=\a∈ A a← B∈ K,\ B I\. This operator is represented by sequential composition in the sense that TK(I)=KIT_K(I)=KI for every interpretation I; see [3, Thm. 35]. Hence the bottom-up iteration of TKT_K from the empty interpretation is given by TKn(∅)=Kn∅T_K^n( )=K^n for every n≥0n≥ 0. It is well-known that the least model of a logic program is obtained by a least fixed point iteration of its van Emden-Kowalski operator [17]. Therefore, LM(K)=⋃n≥1TKn(∅)=⋃n≥1Kn∅=Kω.LM(K)= _n≥ 1T_K^n( )= _n≥ 1K^n =K^ω. ∎ 6.1. Omega and composition A natural question is how the ω-operator behaves with respect to sequential composition. The following theorem provides an explicit formula for the least model of a composition KLKL, showing that it can be computed entirely from the proper and factual components of the factors. Corollary 19. For any Krom programs K and L, (30) (KL)ω=p(KL)∗f(K)∪p(KL)∗p(K)f(L). (KL)^ω=p(KL) f(K)∪ p(KL) p(K)f(L). Proof. By the formula for the ω-operator in (28) applied to KLKL, we have (KL)ω=p(KL)∗f(KL)=11,19p(KL)∗(f(K)∪p(K)f(L))=7p(KL)∗f(K)∪p(KL)∗p(K)f(L). (KL)^ω=p(KL) f(KL) eq:p(KL), eq:f(KL)=p(KL) (f(K)∪ p(K)f(L)) eq:M(K_cup_L)=p(KL) f(K)∪ p(KL) p(K)f(L). ∎ 6.2. Omega and set union The explicit characterization of the ω-operator obtained above immediately yields corresponding formulas for compound programs. We consider here the interaction of ω with set union and derive an expression for the least model of the union of two Krom programs in terms of the least models of its parts. Corollary 20. For any Krom programs K and L, (31) (K∪L)ω=p(K∗L)∗Kω∪p(L∗K)∗Lω. (K∪ L)^ω=p(K L) K^ω∪ p(L K) L^ω. Proof. By the formula for the ω-operator in (28) applied to K∪LK∪ L, we have (K∪L)ω (K∪ L)^ω =p(K∪L)∗f(K∪L) =p(K∪ L) f(K∪ L) =(p(K)∪p(L))∗(f(K)∪f(L)) =(p(K)∪ p(L)) (f(K)∪ f(L)) =7(p(K)∪p(L))∗f(K)∪(p(K)∪p(L))∗f(L) eq:M(K_cup_L)=(p(K)∪ p(L)) f(K)∪(p(K)∪ p(L)) f(L) =24(p(K)∗p(L))∗p(K)∗f(K)∪(p(L)∗p(K))∗p(L)∗f(L) eq:(K_cup_L)^ast=(p(K) p(L)) p(K) f(K)∪(p(L) p(K)) p(L) f(L) =28(p(K)∗p(L))∗Kω∪(p(L)∗p(K))∗Lω eq:K^omega=(p(K) p(L)) K^ω∪(p(L) p(K)) L^ω =23(p(K∗)p(L))∗Kω∪(p(L∗)p(K))∗Lω eq:p(K^ast)=(p(K )p(L)) K^ω∪(p(L )p(K)) L^ω =11p(K∗L)∗Kω∪p(L∗K)∗Lω. eq:p(KL)=p(K L) K^ω∪ p(L K) L^ω. ∎ Corollary 21. For any Krom program K and interpretation I, (32) (K∪I)ω=Kω∪p(K)∗I. (K∪ I)^ω=K^ω∪ p(K) I. Proof. (K∪I)ω (K∪ I)^ω =28p(K∪I)∗f(K∪I) eq:K^omega=p(K∪ I) f(K∪ I) =10,15(p(K)∪p(I))∗(f(K)∪f(I)) eq:p(K_cup_L), eq:f(K_cup_L)=(p(K)∪ p(I)) (f(K)∪ f(I)) =p(K)∗(f(K)∪I) =p(K) (f(K)∪ I) =p(K)∗f(K)∪p(K)∗I =p(K) f(K)∪ p(K) I =28Kω∪p(K)∗I. eq:K^omega=K^ω∪ p(K) I. ∎ 7. Permutation programs This brief section is concerned with permutations and their representation as Krom programs: Definition 22. We associate with every permutation π:A→Aπ:A→ A the permutation program Kπ:=π(a)←a∣a∈A. K_π:=\π(a)← a a∈ A\. We denote the set of all permutation programs over A by ΠA _A. Example 23. Let A:=a,b,c,dA:=\a,b,c,d\. Then the Krom program K(ab)(cd)=a←b←ac←d←c K_(ab)(cd)= \ array[]ca← b\\ b← a\\ c← d\\ d← c array \ is the permutation program corresponding to the permutation (ab)(cd)(ab)(cd) written in cycle notation. Theorem 24. For any permutations π and θ of A, we have KπKθ K_πK_θ =Kπθ =K_πθ KidA K_id_A =1A =1_A Kπ−1 K_π^-1 =Kπd, =K_π^d, where the dual KπdK_π^d is obtained from KπK_π by reverting all arrows in KπK_π.444This is not a problem since KπK_π consists only of proper rules. That is, the mapping π↦Kπ K_π is a group isomorphism from the permutation group SAS_A over A to the group of all permutation programs over A thus showing (SA,∘,idA,)−1≅(ΠA,∘,1A,)d. (S_A, ,id_A,^-1) ( _A, ,1_A,^d). Proposition 25. Two distinct permutation programs are never subsumption equivalent. Proof. Let KπK_π and KσK_σ be two distinct permutation programs over an alphabet A. Then there exists an atom a∈Aa∈ A such that π(a)≠σ(a)π(a)≠σ(a). Hence Kπ∘a=π(a)K_π \a\=\π(a)\ and Kσ∘a=σ(a).K_σ \a\=\σ(a)\. Since π(a)≠σ(a)π(a)≠σ(a), it follows that Kπ∘a≠Kσ∘a,K_π \a\≠ K_σ \a\, which implies Kπ≢ssKσ.K_π _sK_σ. ∎ 8. Generators and canonical decompositions In this section, we investigate generating sets for finite Krom seminearrings from two complementary perspectives. First, by fixing an enumeration of the underlying finite alphabet, we construct a natural generating set that yields shortest decompositions of singleton Krom programs and hence canonical decompositions of arbitrary Krom programs as unions of such singleton decompositions. Second, we show that, despite the size of this canonical generating set, every finite Krom seminearring can in fact be generated by only three elements. Thus, while canonical decompositions require a richer collection of generators, remarkably compact generating sets also exist. Theorem 26. Fix an enumeration A=a0,…,anA=\a_0,…,a_n\, n≥0n≥ 0, of a finite alphabet A. Let A:=(A,∪,∘,∅,1A) K_A:=(K_A,∪, , ,1_A) be the corresponding finite Krom seminearring. The set (33) A:=a0∪ai+1←ai∣0≤i≤n−1∪a0←an _A:=\\a_0\\∪\\a_i+1← a_i\ 0≤ i≤ n-1\∪\\a_0← a_n\\ generates AK_A as a seminearring. Moreover, every Krom program is a union of shortest decompositions of singleton Krom programs over AG_A. Proof. Consider the directed cycle a0→a1→⋯→an→a0a_0→ a_1→·s→ a_n→ a_0 induced by the proper-rule generators in AG_A. For 0≤i,j≤n0≤ i,j≤ n, let d(i,j)d(i,j) denote the length of the unique directed path from aia_i to aja_j in this cycle. First, every singleton fact ai\a_i\ belongs to the subseminearring generated by AG_A. Indeed, for i=0i=0 this is immediate since a0∈A\a_0\ _A, and for 1≤i≤n1≤ i≤ n we have ai \a_i\ =ai←ai−1∘⋯∘a1←a0∘a0. =\a_i← a_i-1\ ·s \a_1← a_0\ \a_0\. This decomposition uses exactly d(0,i)d(0,i) proper-rule generators. Next, let aj←ai\a_j← a_i\ be a proper singleton Krom program. If i<ji<j, then aj←ai \a_j← a_i\ =aj←aj−1∘⋯∘ai+1←ai, =\a_j← a_j-1\ ·s \a_i+1← a_i\, which uses exactly d(i,j)=j−id(i,j)=j-i generators. If j<ij<i, then the unique directed path from aia_i to aja_j passes through ana_n and wraps around to a0a_0, yielding aj←ai \a_j← a_i\ =aj←aj−1∘⋯∘a1←a0∘a0←an∘an←an−1∘⋯∘ai+1←ai, =\a_j← a_j-1\ ·s \a_1← a_0\ \a_0← a_n\ \a_n← a_n-1\ ·s \a_i+1← a_i\, which uses exactly d(i,j)=n−i+j+1d(i,j)=n-i+j+1 generators. Hence every singleton Krom program can be expressed in terms of AG_A. Since every Krom program is the union of its singleton subprograms, it follows that AG_A generates AK_A as a seminearring. It remains to prove that the above decompositions are shortest. Every proper-rule generator corresponds to exactly one edge of the directed cycle a0→a1→⋯→an→a0.a_0→ a_1→·s→ a_n→ a_0. Thus every composition of m proper-rule generators corresponds to a directed path of length m. Consequently, no singleton rule aj←ai\a_j← a_i\ can be obtained using fewer than d(i,j)d(i,j) proper-rule generators. Similarly, no singleton fact ai\a_i\ can be obtained using fewer than d(0,i)d(0,i) proper-rule generators together with the unique fact generator a0\a_0\. Hence all singleton decompositions displayed above are shortest. Finally, let K∈AK _A be arbitrary. Since composition distributes over set union, every decomposition of K over AG_A can be rewritten as a union of compositions representing singleton Krom programs. By the arguments above, each such singleton decomposition must have length at least equal to the corresponding directed distance. Hence replacing every singleton subprogram of K by its shortest decomposition yields a shortest decomposition of K. Therefore every Krom program is a union of shortest decompositions of its singleton Krom subprograms over AG_A. ∎ Proposition 27. The generating set AG_A in (33) is minimal. Proof. We show that no element of AG_A can be generated by the remaining ones. First, the generator a0\a_0\ cannot be omitted, since all other generators are proper programs and the composition and union of proper programs is again proper. Hence no fact can be generated without a0\a_0\. Next, fix 0≤i≤n−10≤ i≤ n-1. If the generator ai+1←ai\a_i+1← a_i\ is removed, then every remaining proper-rule generator corresponds to an edge of the directed cycle a0→a1→⋯→an→a0a_0→ a_1→·s→ a_n→ a_0 except for the edge from aia_i to ai+1a_i+1. Since composition of singleton proper rules corresponds to concatenation of directed paths, every proper singleton rule generated by the remaining proper-rule generators corresponds to a directed path in the cycle with this edge removed. But there is no directed path from aia_i to ai+1a_i+1 in this graph. Therefore ai+1←ai\a_i+1← a_i\ cannot be generated by the remaining generators. The same argument applies to the generator a0←an\a_0← a_n\: if it is removed, then the edge from ana_n to a0a_0 is missing, and there is no directed path from ana_n to a0a_0 using the remaining proper-rule generators. Hence a0←an\a_0← a_n\ cannot be generated by the remaining generators. Thus no generator in AG_A lies in the subseminearring generated by the other generators. Therefore AG_A is minimal. ∎ Proposition 28. For every alphabet A with |A|≥2|A|≥ 2, the finite Krom seminearring A K_A is generated by three elements. Proof. Fix an enumeration A=a0,…,anA=\a_0,…,a_n\ with n≥1n≥ 1, and define C:=ai+1←ai∣0≤i<n∪a0←an,C:=\a_i+1← a_i 0≤ i<n\∪\a_0← a_n\, E:=a0←a0,E:=\a_0← a_0\, and F:=a0.F:=\a_0\. We claim that C,E,FC,E,F generate AK_A. Using indices modulo n+1n+1, the program C represents the cyclic permutation ai↦ai+1a_i a_i+1. Hence, Cr=ai+r←ai∣0≤i≤n C^r=\a_i+r← a_i 0≤ i≤ n\ for every r≥0r≥ 0. Therefore, for all 0≤i,j≤n0≤ i,j≤ n, we have Cj∘E∘Cn+1−i C^j E C^n+1-i =aj←ai. =\a_j← a_i\. Thus every proper singleton Krom program is generated by C and E. Moreover, for every 0≤j≤n0≤ j≤ n, we have Cj∘E∘F C^j E F =aj. =\a_j\. Hence every singleton fact is generated by C,E,FC,E,F. Since every Krom program is a finite union of singleton Krom programs, it follows that C,E,FC,E,F generate AK_A. ∎ 9. Automata In this section, we show that finite Krom monoids have enough algebraic structure to represent finite-state machines. More precisely, we establish that every deterministic semiautomaton naturally gives rise to a Krom monoid isomorphic to its transformation monoid. Recall that a (deterministic) semiautomaton is a triple =(Q,Σ,δ) A=(Q, ,δ), where Q is a finite set of states, Σ is a finite alphabet, and δ:Q×Σ→Qδ:Q× → Q is the transition function. For every a∈Σa∈ , define the Krom program Ka:=δ(q,a)←q∣q∈Q,K_a:=\δ(q,a)← q q∈ Q\, and extend this assignment recursively to words by Kε K_ :=1Q, :=1_Q, Kuv K_uv :=Ku∘Kv, :=K_u K_v, where ε denotes the empty word and u,v∈Σ∗u,v∈ . Similarly, define δε _ :=idQ, :=id_Q, δuv _uv :=δu∘δv, := _u _v, and let :=(δw∣w∈Σ∗,∘,δε) T_ A:=(\ _w w∈ \, , _ ) denote the transformation monoid of A. Furthermore, let :=Kw∣w∈Σ∗K_ A:=\K_w w∈ \ and define the associated Krom monoid by :=(,∘,1Q). K_ A:=(K_ A, ,1_Q). We then have the following correspondence between the Krom monoid and the transformation monoid of a semiautomaton: Theorem 29. The mapping Kw↦δw,K_w _w, for w∈Σ∗w∈ is a monoid isomorphism from K_ A onto the transformation monoid T_ A. We now turn our attention to deterministic finite automata. Recall that such an automaton is a tuple =(Q,Σ,δ,q0,F) A=(Q, ,δ,q_0,F), where (Q,Σ,δ)(Q, ,δ) is a semiautomaton, q0∈Qq_0∈ Q is the initial state, and F⊆QF Q is the set of final states. Its behavior is given by ‖:=w∈Σ∗∣δ(q0,w)∈F.|| A||:=\w∈ δ(q_0,w)∈ F\. The above theorem immediately yields the following characterization: Proposition 30. For every deterministic finite automaton =(Q,Σ,δ,q0,F) A=(Q, ,δ,q_0,F), ‖=w∈Σ∗∣F∩(Kw∘q0)≠∅.|| A||=\w∈ F∩(K_w q_0)≠ \. Proof. By construction, Kw=δ(q,w)←q∣q∈Q.K_w=\δ(q,w)← q q∈ Q\. Since A is deterministic, for every state q∈Qq∈ Q the program KwK_w contains exactly one rule whose body is q, namely δ(q,w)←qδ(q,w)← q. In particular, Kw∘q0=δ(q0,w).K_w q_0=\δ(q_0,w)\. Consequently, F∩(Kw∘q0)≠∅F∩(K_w q_0)≠ if and only if δ(q0,w)∈F,δ(q_0,w)∈ F, which is equivalent to w∈‖.w∈|| A||. ∎ Corollary 31. Every finite monoid is isomorphic to a submonoid of a finite Krom monoid. Proof. By the Cayley theorem for monoids, every finite monoid is isomorphic to a submonoid of a finite transformation monoid. Furthermore, every finite transformation monoid is the transformation monoid of a finite semiautomaton and is therefore, by Theorem 29, isomorphic to a finite Krom monoid. The result now follows by composition of the two embeddings. ∎ 10. Conclusion In this paper, we investigated the algebraic structure induced by sequential composition on propositional Krom logic programs. We showed that, despite their syntactic simplicity, Krom programs give rise to a remarkably rich collection of algebraic structures, including monoids, seminearrings, quemirings, and Conway seminearrings and omegaseminearrings. Along the way, we established explicit generating sets and canonical decompositions, analyzed the interaction of sequential composition with the facts, proper-rule, Kleene star, and ω-operators, and related Krom programs to directed graphs, transformation monoids, and finite-state automata. These results provide further evidence that logic programs can be studied fruitfully from an algebraic perspective. In particular, the occurrence of Conway identities and graph-theoretic interpretations suggests close connections with semiring-based automata theory and algebraic graph theory. Moreover, the fact that Krom programs arise as the basic components in the Minimalist Decomposition Theorem for Horn programs [5] provides further motivation for investigating their algebraic structure. The present work raises several directions for future research. A natural next step is to investigate homomorphisms, congruences, and quotient constructions for logic program algebras and to develop a corresponding representation theory. It would also be interesting to extend the algebraic techniques developed here beyond the Krom fragment and to study analogous structures for richer classes of logic programs and answer set programs. References [1] Antić, C. On cascade products of answer set programs. Theory and Practice of Logic Programming 14, 4-5 (2014), 711–723. https://doi.org/10.1017/S1471068414000301. [2] Antić, C. Sequential composition of answer set programs. https://arxiv.org/pdf/2104.12156.pdf, 2024. [3] Antić, C. Sequential composition of propositional logic programs. Annals of Mathematics and Artificial Intelligence 92, 2 (2024), 505–533. https://doi.org/10.1007/s10472-024-09925-x. [4] Antić, C. Logic program proportions. Annals of Mathematics and Artificial Intelligence 93 (2025), 321–342. https://doi.org/10.1007/s10472-023-09904-8. [5] Antić, C. Set-like operations on propositional logic programs. Theory and Practice of Logic Programming (2026). https://arxiv.org/pdf/2605.03613, accepted. [6] Apt, K. R. Logic programming. In Handbook of Theoretical Computer Science, J. van Leeuwen, Ed., vol. B. Elsevier, Amsterdam, 1990, p. 493–574. [7] Brogi, A., Mancarella, P., Pedreschi, D., and Turini, F. Modular logic programming. ACM Transactions on Programming Languages and Systems 16, 4 (1999), 1361–1398. [8] Bugliesi, M., Lamma, E., and Mello, P. Modularity in logic programming. The Journal of Logic Programming 19-20, 1 (1994), 443–502. [9] Conway, J. H. Regular Algebra and Finite Machines. Chapman and Hall, 1971. [10] Elgot, C. C. Matrical theories. Journal of Algebra 42, 2 (1976), 391–422. [11] Ésik, Z., and Kuich, W. Modern Automata Theory. http://w.dmg.tuwien.ac.at/kuich/mat.pdf, 2006. [12] Knauer, U. Algebraic Graph Theory. Morphisms, Monoids, and Matrices. De Gruyter, Berlin, 2011. [13] Krom, M. R. The decision problem for a class of first-order formulas in which all disjunctions are binary. Mathematical Logic Quarterly 13, 1-2 (1967), 15–20. [14] Lloyd, J. W. Foundations of Logic Programming, 2 ed. Springer-Verlag, Berlin, Heidelberg, 1987. [15] Makowsky, J. A. Why Horn formulas matter in computer science: initial structures and generic examples. Journal of Computer and System Sciences 34, 2-3 (1987), 266–292. [16] O’Keefe, R. A. Towards an algebra for constructing logic programs. In SLP 1985. 1985, p. 152–160. [17] van Emden, M. H., and Kowalski, R. The semantics of predicate logic as a programming language. Journal of the ACM 23, 4 (1976), 733–742. [18] van Hoorn, W. G., and van Rootselaar, B. Fundamental notions in the theory of seminearrings. Compositio Mathematica 18, 1-2 (1967), 65–78.