Multi-Domain Propagation Algebra (MDPA)

Multi-Domain Propagation Algebra (MDPA 2.0) A Relational Framework for Multi-Domain Propagation Jos´e Fabi´an Soltero Escobar November 15, 2025 Abstract Multi-Domain Propagation Algebra (MDPA 2.0) is an algebraic framework for reasoning about propagation, reachability, and influence across multiple, typed domains. The structure is built over a family of sets (domains) and typed relations RA,B ⊆A×Bbetween them. A distinguished global propagation operator T={TA,B}specifies one-step propagation across domains, and a globally coupled closure T∗={T∗ A,C }is defined as the least fixed point of a monotone functional over a product of hom-sets, in the style of lattice-theoretic fixed-point constructions [4, 7]. The axioms require complete hom-posets, monotone and associative composition, and star-unfold laws characterizing the closure. The framework admits a categorical interpretation as a Rel-enriched, multi-sorted structure equipped with a singled-out global fixedpoint operator [3, 6]. In the finite case, a typed Boolean block–Warshall algorithm [5] computes the global closure T∗. 1 Introduction & Motivation Many systems of practical interest are inherently multi-domain: they involve several distinct spaces of entities—users, resources, geographical regions, components, logical states—with relations linking elements across domains. Typical questions in such systems concern propagation: •which states become reachable from an initial configuration, •which resources become accessible from a given user, •how influence or information flows across a heterogeneous network. This paper presents a formal specification of the Multi-Domain Propagation Algebra (MDPA), an algebraic framework for multi-domain propagation and reachability in such settings. MDPA 2.0 is designed to model systems with multiple typed domains A, B, C, . . . and typed relations RA,B ⊆A×Bbetween them. A distinguished propagation family T={TA,B}encodes one-step transitions, while a globally coupled closure T∗={T∗ A,C}captures multi-step propagation across heterogeneous paths involving several intermediate domains. The definition of T∗is based on a fixed-point construction over a product of hom-sets. For each target domain C, the family of relations (−, C) is treated as a point of a complete product lattice, and the closure column T∗ −,C := (T∗ A,C)A∈O arises as the least fixed point of a monotone functional on that lattice. This design makes explicit that propagation is coupled across domains: each T∗ A,C depends on all intermediate relations T∗ B,C . 1 The rest of the paper is organized as follows. Section 2 introduces preliminaries and conventions on typed relations. Section 3 gives the formal definition of MDPA. Section 4 develops the fixed-point construction of T∗. Section 5 lists the axioms. Section 6 presents the categorical interpretation. Section 7 describes the finite case and a Boolean block–Warshall algorithm. Section 8 provides a worked example. An appendix states a fixed-point lemma in a typed, product form. 2 Preliminaries & Conventions All sets are assumed small. For finite domains, Boolean matrices are used. 2.1 Typed domains and relations Afamily of domains is a set Otogether with a set Afor each A∈O. We use the same symbol A for the domain and its underlying set when no confusion arises. For each pair of domains A, B ∈Owe write RA,B := P(A×B) for the hom-set of typed relations from Ato B. Elements R∈RA,B are subsets R⊆A×B. The hom-poset (RA,B,⊆) is ordered by inclusion and is a complete lattice: arbitrary unions exist, and we write SSfor the supremum of a family S ⊆ RA,B. 2.2 Typed union Unions are only formed within a hom-set. If R⊆A×Band S⊆C×Dwith (A, B)= (C, D), then R∪Sis not regarded as a typed morphism either A→Bor C→D; it may be viewed as a disjoint family-level union but does not belong to a single RA,B or RC,D. For R, S ∈RA,B, we write R∪S∈RA,B for the usual set-theoretic union. Within a fixed hom-set, union forms an idempotent commutative semilattice with bottom 0A,B := ∅. 2.3 Relational composition For R⊆A×Band S⊆B×C, the (relational) composition S◦R⊆A×C is defined by (a, c)∈S◦R⇐⇒ ∃b∈B. (a, b)∈R∧(b, c)∈S. Composition is only defined when the middle type matches; ill-typed expressions are left undefined. In what follows we work only with well-typed compositions. Associativity and the existence of identities are assumed and made explicit in Section 5. 2 2.4 Identities and zero For each domain A∈O, IA:= {(a, a)|a∈A}⊆A×A is the identity relation on A. For each pair (A, B), 0A,B := ∅ ⊆ A×B is the zero relation. We write I:= {IA}A∈O,0 := {0A,B}A,B∈O. These conventions underpin the use of Tarski’s fixed-point theorem, both in the general and in the finite case [4, 7]. 3 Formal Definition of MDPA We now introduce the main structure of this paper. Definition 3.1 (Multi-Domain Propagation Algebra).AMulti-Domain Propagation Algebra (MDPA) is a tuple M= (O, R, T, ◦,∪, T∗,I,0), where: •Ois a set of domains. •For each A, B ∈O, RA,B := P(A×B) is the hom-set of typed relations from Ato B, and R:= {RA,B}A,B∈O denotes the family of hom-sets. •For R∈RA,B and S∈RB,C , composition S◦R∈RA,C is standard relational composition. Composition is associative and admits identities IA∈RA,A. •For R, S ∈RA,B, union R∪S∈RA,B is the set-theoretic union. Each hom-poset (RA,B,⊆) is a complete lattice under inclusion. •For each A, B ∈O, 0A,B := ∅ ∈ RA,B is the zero relation. •T={TA,B ∈RA,B |A, B ∈O}is a distinguished propagation operator: a typed family of one-step propagators. 3 •T∗={T∗ A,C ∈RA,C |A, C ∈O}is the global propagation closure induced by T, defined as the least fixed point of a monotone functional over a product of hom-sets, as described in Section 4. Remark 3.2.The symbol ∗is reserved for the global closure T∗. No general star operation R7→ R∗ is assumed on arbitrary relations R∈RA,B, in contrast to the setting of Kleene algebras [1, 2]. Remark 3.3 (Concrete model and axiomatization).Throughout this paper we work in the concrete relational model where RA,B =P(A×B) and composition is standard relational composition. The axioms in Section 5 are satisfied by this model and can be read as an axiomatization of its behaviour. 4 Fixed-Point Construction of T∗ This section gives the fixed-point construction of T∗. The key idea is that closure is defined simultaneously across all source domains for a fixed target domain, using a product lattice. 4.1 Product lattices Fix a target domain C∈O. Define R−,C := Y B∈O P(B×C). An element R∈R−,C is a family R= (RB,C )B∈O, RB,C ⊆B×C. Equip R−,C with the pointwise order: R≤S⇐⇒ ∀B∈O. RB,C ⊆SB,C . Since each P(B×C) is a complete lattice under inclusion, the product R−,C is a complete lattice under ≤. 4.2 Diagonal identity component For A, C ∈Odefine a typed identity component IA,C := (IAif A=C, ∅otherwise. Thus IA,C ⊆A×C, and reflexivity contributes only along the diagonal A=C. 4.3 Local and global functionals For A, C ∈O, define a functional FA,C :R−,C → P(A×C) by FA,C(R) := IA,C ∪[ B∈OTA,B ◦RB,C . 4 This operator takes as input a column-family R= (RB,C )B∈Oand produces a relation A→C obtained by adding the diagonal identity (when A=C) and one-step propagation via T. To treat all sources Asimultaneously for a fixed target C, define the global functional FC:R−,C →R−,C by FC(R) := FA,C(R)A∈O. Thus, for each A∈O, FC(R)A=IA,C ∪[ B∈OTA,B ◦RB,C . 4.4 Monotonicity Lemma 4.1 (Monotonicity of FC).For each fixed C∈O, the functional FC: (R−,C,≤)→(R−,C,≤) is monotone. Proof. Let R, S ∈R−,C with R≤S, i.e. RB,C ⊆SB,C for all B∈O. For each A∈Owe have FA,C(R) = IA,C ∪[ B∈OTA,B ◦RB,C ⊆IA,C ∪[ B∈OTA,B ◦SB,C =FA,C (S), using monotonicity of relational composition and of union. Thus FC(R)A⊆FC(S)Afor each A, whence FC(R)≤FC(S). 4.5 Least fixed point and definition of T∗ By Tarski’s fixed-point theorem [4], a monotone self-map on a complete lattice has a least fixed point. Theorem 4.2 (Existence of global propagation closure).For each C∈O, the functional FChas a least fixed point µFC∈R−,C. Write T∗ −,C := µFC,and T∗ A,C := (T∗ −,C)Afor all A∈O. Then the family T∗={T∗ A,C}A,C∈Ois the global propagation closure induced by T. 4.6 Unfold laws and shorthand notation From µFC=FC(µFC) we obtain, for each A, C ∈O, T∗ A,C =IA,C ∪[ B∈OTA,B ◦T∗ B,C . A dual argument (see Appendix A) gives the corresponding right-unfold law T∗ A,C =IA,C ∪[ B∈OT∗ A,B ◦TB,C , where again IA,C contributes only when A=C. 5 Lemma 4.3 (Star unfold laws).For all A, C ∈O, T∗ A,C =IA,C ∪[ B∈OTA,B ◦T∗ B,C , T∗ A,C =IA,C ∪[ B∈OT∗ A,B ◦TB,C . Moreover, T∗is the least family of relations satisfying these equations. Remark 4.4 (Shorthand µ-notation).In informal reasoning it is convenient to write T∗ A,C =µR. IA,C ∪[ B∈O TA,B ◦RB,C , where Rranges over families (RB,C )B∈O. This should be understood as referring to the A, Ccomponent of the global least fixed point µFCon the product lattice R−,C. 5 Axioms We now collect the algebraic laws assumed in a Multi-Domain Propagation Algebra. These axioms are stated hom-set by hom-set and are consistent with the fixed-point construction of T∗in Section 4, in the spirit of equational/algebraic approaches to program semantics and reachability [1, 2]. Let A, B, C, D range over O. 1. Associativity of composition. For R⊆A×B,S⊆B×Cand U⊆C×D, (U◦S)◦R=U◦(S◦R) as subsets of A×D. 2. Identity laws. For any R⊆A×B, IA◦R=R=R◦IB. 3. Union laws. For R, S, U ∈RA,B, R∪S=S∪R, (R∪S)∪U=R∪(S∪U), R ∪R=R. 4. Distributivity. For R∈RA,B and S, U ∈RB,C, R◦(S∪U)=(R◦S)∪(R◦U). 5. Monotonicity of composition. If RA,B ⊆SA,B and UB,D ⊆VB,D, then UB,D ◦RA,B ⊆VB,D ◦SA,B. 6. Completeness of hom-posets. For each A, B ∈O, RA,B =P(A×B) is a complete lattice under inclusion, closed under arbitrary unions. 6 7. Global propagation closure. The family T∗={T∗ A,C}is defined as in Theorem 4.2: for each C∈O, T∗ A,C = (µFC)A with FCthe monotone functional over the product lattice R−,C . 8. Star unfold laws. For all A, C ∈O, T∗ A,C =IA,C ∪[ B∈O (TA,B ◦T∗ B,C ), T∗ A,C =IA,C ∪[ B∈O (T∗ A,B ◦TB,C ), and T∗is the least family of relations satisfying these equations. 6 Categorical Interpretation The hom-posets (RA,B,⊆) in a Multi-Domain Propagation Algebra form a Rel-enriched structure with an additional global fixed-point operator. 6.1 Rel-enriched structure From Definition 3.1 and the axioms in Section 5 we obtain: •Objects are the domains A∈O. •Hom-sets are RA,B =P(A×B), each a complete lattice under inclusion. •Composition is relational composition ◦with identities IAand zeros 0A,B. •Composition is monotone in both arguments and distributes over finite unions. This situates the underlying relational layer of MDPA within the general picture of categories enriched in the quantale (2,≤,∧,∨) and of allegorical approaches to relations [3, 6]. 6.2 Global fixed-point operator The presence of a distinguished propagation operator T={TA,B}and its globally coupled closure T∗={T∗ A,C}augments this Rel-enriched structure with a singled-out fixed-point operator, defined via Tarski’s theorem over product lattices R−,C [4, 7]. Propagation is thus treated as a first-class algebraic component: the relations TA,B encode onestep transitions, and the family T∗ A,C is determined uniquely as the least fixed point of the global functional FCfor each target domain C. Remark 6.1 (Level of generality).The development in this paper is phrased in the concrete setting where hom-sets are powersets P(A×B) with standard relational composition. The same construction extends to more general relational settings (such as allegories or Rel-enriched categories) provided suitable suprema exist; we do not pursue this generalization here. 7 7 Finite Case and Boolean Block–Warshall In this section we consider the case where each domain A∈Ois finite. Relations are then represented as Boolean matrices, and the global closure T∗can be computed by a typed Boolean block–Warshall algorithm [5]. 7.1 Matrix representation Assume all domains A∈Oare finite with |A|=nA. Fix an enumeration of each Aso that elements are indexed by {1, . . . , nA}. For each A, B ∈O, a relation RA,B ⊆A×Bis represented by a Boolean matrix M[A, B] of size nA×nB: M[A, B]i,j =(true if the i-th element of Ais related to the j-th element of B, false otherwise. The global propagation operator Tis represented by a family {M[A, B]}A,B∈Owhere M[A, B] = adjacency(TA,B). Boolean matrix multiplication is defined using ∨as addition and ∧as multiplication. We write ⊙for this product. 7.2 Initialization We initialize blocks as M[A, B] = (adjacency(TA,B) if TA,B is given, zero matrix of size nA×nBotherwise, encoding the propagation operator T. We then incorporate reflexive closure on each diagonal block: for A in O: M[A, A] := M[A, A] OR I_A where IAis represented as the identity matrix of size nA. 7.3 Typed Boolean block–Warshall algorithm We perform a typed Boolean block–Warshall procedure over the index set O. One sweep of the algorithm is: for k in O: for A in O: for B in O: if (A,k) in M and (k,B) in M: if (A,B) not in M: M[A,B] := zero_matrix(|A|, |B|) M[A,B] := M[A,B] OR (M[A,k] @ M[k,B]) In practice, this sweep is repeated until saturation, i.e. until no block M[A, B] changes. At the level of relations, the algorithm constructs an ascending chain in the finite product lattice of Boolean blocks. 8 Proposition 7.1 (Finite correctness).Assume each A∈Ois finite. Then the typed Boolean block– Warshall procedure terminates and returns, for each A, C ∈O, the Boolean matrix representing T∗ A,C as defined by Theorem 4.2. Sketch. The family of Boolean blocks {M[A, B]}A,B∈Oforms a finite product lattice under the pointwise order induced by the entrywise order on {false,true}. Each update step M[A, B]7→ M[A, B]∨(M[A, k]⊙M[k, B]) is monotone in this lattice. Thus the algorithm generates an ascending chain, which must stabilize after finitely many steps. The limit is a fixed point of the family of global functionals {FC}C∈Oat the matrix level. By uniqueness of the least fixed point, each column of this limit coincides with the least fixed point µFCdescribed in Theorem 4.2, hence the resulting blocks represent the closure T∗. 8 Worked Example We illustrate the typed Boolean block–Warshall procedure in a simple three-domain setting using Python and NumPy. Consider domains A, B, C with |A|=|B|= 2 and |C|= 3, and non-trivial propagation steps TA,B and TB,C . 8.1 Setup The following Python code initializes Boolean matrices for these relations and performs one sweep of the block–Warshall algorithm. Repeating until no changes occur yields a representation of T∗. import numpy as np nA, nB, nC = 2, 2, 3 Z = lambda m, n: np.zeros((m, n), dtype=bool) # Initialize matrices for each typed relation 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’] # Reflexive closure for X in O: M[(X,X)] |= np.eye(M[(X,X)].shape[0], dtype=bool) # Typed Boolean block--Warshall 9