Multi-Domain Propagation Algebra (MDPA)

Multi-Domain Propagation Algebra (MDPA) José Fabián Soltero Escobar October 29, 2025 Abstract The Multi-Domain Propagation Algebra (MDPA) extends classical Kleene Algebra to a typed, multi-domain setting where relations connect distinct spaces and propagation enables reachability across heterogeneous domains. MDPA provides a minimal algebraic foundation for reasoning about propagation, reachability, and influence flow in distributed or typed relational systems, bridging algebraic, categorical, and implementational perspectives. 1 Assumptions and Conventions All sets are assumed small. For finite domains, Boolean matrices are used. Order on each hom-set ( RA,B,⊆ )is by inclusion; each is in fact a complete lattice, since RA,B = P ( A×B )admits arbitrary unions. Union ∪ is componentwise and forms an idempotent commutative semilattice with bottom 0 A,B . This completeness underlies the use of Tarski’s fixed-point theorem in the finite and general cases. Composition is monotone in both arguments. Typed union. Unions are only formed within a hom-set: if R⊆A×B and S⊆C×D with ( A, B )  = ( C, D ), then R∪S is undefined (or treated as disjoint at the family level, not as a typed morphism). 2 Motivation Classical Kleene Algebras operate over a single universe X with R⊆X×X . Many systems (security, logistics, dataflow, control) involve heterogeneous domains—users, resources, or spaces—where relations are cross-domain. MDPA generalizes Kleene Algebra by: •Typed relations R⊆A×Bacross distinct domains. •A closure operator T∗capturing propagation across multiple spaces. •Seeds vin one domain with reachability computed in another. 1 3 Formal Definition Definition 3.1 (Multi-Domain Propagation Algebra).AMulti-Domain Propagation Algebra (MDPA) is a tuple M= (O,R,·,∪,∗,I,0) where: •O: a collection of domains (sets). •R={RA,B ⊆A×B}A,B∈O: family of typed relations (hom-sets). •Composition: (RA,B ·SB,C )(a, c)⇐⇒ ∃b∈B: (a, b)∈RA,B ∧(b, c)∈SB,C . •IA={(a, a)|a∈A}: identity on A. •0A,B =∅: empty relation. Typed convention. Composition is defined only for composable types; otherwise it yields 0A,C. Each hom-set (RA,B,⊆)is a complete lattice, closed under arbitrary unions. Global Propagation Operator. T={TA,B ⊆A×B|A, B ∈ O}. 4 Axioms We state laws within the appropriate hom-sets. 1. Associativity: For R⊆A×B,S⊆B×C,U⊆C×D, (R·S)·U=R·(S·U). 2. Identities: IA·R=R=R·IB. 3. Union Laws: R∪S=S∪R,(R∪S)∪U=R∪(S∪U),R∪R=R. 4. Distributivity: R·(S∪U) = (R·S)∪(R·U). 5. Monotonicity: If RA,B ⊆SA,B and UB,D ⊆VB,D, then RA,B ·UB,D ⊆SA,B ·VB,D. 6. Star Definition (typed): T∗ A,C =µR. IA∪(T·R)A,C ,(T·R)A,C =[ B∈O TA,B ·RB,C . Lemma 4.1 (Star Unfold Laws).For all A, C ∈ O, T∗ A,C =IA∪[ B∈O (TA,B ·T∗ B,C ), T∗ A,C =IC∪[ B∈O (T∗ A,B ·TB,C ). The second (right-unfold) follows by duality, or equivalently by defining the fixed-point operator dually as R7→ IC∪(R·T). 2 5 Categorical Interpretation Each hom-poset is assumed complete (see §3.1), ensuring enrichment over the complete quantale (2 ,≤,∧,∨ )and compatibility with Tarski’s fixed-point construction. MDPA thus forms a Relenriched category, equivalently a multi-sorted allegory equipped with a least fixed-point operator. 6 Matrix Representation and Implementation Initialize blocks as: M[A, B] = adjacency(TA,B)if defined, else the zero matrix of size |A|×|B|. Then T∗is the Boolean transitive closure of M. Reflexive closure. for A∈ O :M[A, A] := M[A, A]∨IA Boolean block–Warshall (typed). Repeat until saturation: M[A, B] := M[A, B]∨(M[A, k]⊙M[k, B]). Proposition 6.1 (Completeness in the finite case).Assume all objects in O are finite. Then the typed block–Warshall procedure terminates and returns the least fixed point T∗ A,C of FA,C ( R ) = IA∪SB∈O(TA,B ·RB,C ). Sketch. Termination follows because the Boolean blocks form a finite product lattice and each update is monotone. By Definition A.1, T∗ is the least fixed point. The algorithm’s iterates form an ascending Kleene chain on the product of Boolean lattices; termination follows from finiteness of each block and of O. 7 Worked Example import numpy as np nA,nB,nC = 2,2,3 Z = lambda m,n: np.zeros((m,n),dtype=bool) M={ (’A’,’A’): Z(nA,nA), (’B’,’B’): Z(nB,nB), (’C’,’C’): Z(nC,nC), (’A’,’B’): np.array([[1,0],[1,1]],dtype=bool), (’B’,’C’): np.array([[0,1,0],[1,0,1]],dtype=bool) } O=[’A’,’B’,’C’] for X in O: M[(X,X)] |= np.eye(M[(X,X)].shape[0],dtype=bool) # Note: one sweep shown; repeat until saturation for full closure for k in O: for A in O: for B in O: 3 if (A,k) in M and (k,B) in M: if (A,B) not in M: M[(A,B)] = Z(M[(A,A)].shape[0], M[(B,B)].shape[0]) M[(A,B)] |= (M[(A,k)] @ M[(k,B)]).astype(bool) References References [1] D. Kozen. A completeness theorem for Kleene algebras. Information and Computation, 110(2):366–390, 1994. [2] D. Kozen. Kleene algebra with tests. ACM Transactions on Programming Languages and Systems, 19(3):427–443, 1997. [3] P. Freyd and A. Scedrov. Categories, Allegories. North-Holland, 1990. A Fixed Point Lemma and Continuity Lemma A.1 (Fixed Point Lemma (typed form)).For A, C ∈ O, FA,C(R) = IA∪[ B∈O (TA,B ·RB,C ) is monotone on ( P ( A×C ) ,⊆ ); by Tarski, its least fixed point exists and equals T∗ A,C = µR. FA,C (R). 4