E-Connections

Origin. Oliver Kutz, Carsten Lutz, Frank Wolter, and Michael Zakharyaschev, "E-connections of abstract description systems" (Artificial Intelligence 156, 2004), with the earlier "E-connections of description systems" and Kutz's thesis (2004). Built for a stated purpose: fusion is too weak to say anything and products are undecidable, so the field needed a construction in the gap, and this is the one that was found.

Models. Two logics interpreted over disjoint domains, connected by relations that run between them. A fusion puts both modalities over one domain and lets them ignore each other; a product puts them on the axes of a grid and forces them to commute. An E-connection keeps the domains apart — the spatial regions here, the time points there — and adds link relations E ⊆ Δ₁ × Δ₂ with modal operators along them. The interaction is real: one can say "this region is occupied at some time when φ". And decidability transfers, which is the point.

Formalism.

Components: abstract description systems (ADSs) S₁, …, Sₙ — a common generalization of description logics, modal logics, and many first-order fragments, each with its own domain Δᵢ and its own operators.

The connection: a set E of link relations E ⊆ Δᵢ × Δⱼ for i ≠ j.

Connecting operators: for each link relation E and each concept/formula C of the target component, ⟨E⟩C — the objects of Δᵢ that E-relate to some C-object of Δⱼ Formally, in an interpretation with disjoint domains Δ₁, …, Δₙ and E^I ⊆ Δᵢ × Δⱼ: (⟨E⟩C)^I = {x ∈ Δᵢ : ∃y ((x,y) ∈ E^I ∧ y ∈ C^I)} and the dual [E]C. Only the connecting operators cross; each component's own operators stay inside their domain.

What is expressible: Region ⟨occupies⟩ (Time ⊓ ⟨after⟩ Event) — a spatial concept defined by reference to a temporal one. The link is the only bridge, and it is a bare existential — no commutation, no confluence, no grid.

Transfer (Kutz–Lutz–Wolter–Zakharyaschev 2004): Decidability transfers. If each component's satisfiability problem is decidable, so is the E-connection's. The proof is a quasimodel / mosaic argument: the disjointness of domains means a model can be assembled component-wise, with the link relations reconciled by a finite bookkeeping condition. Complexity is typically the maximum of the components' plus an exponential, not the blow-up products suffer. Adding expressivity to the link language — Booleans on link relations, inverse links, number restrictions on links — recovers some product-like power and loses decidability, and the boundary has been mapped: the point at which E-connections become undecidable is the point at which they can force a grid.

Position between the constructions: fusion ⊊ E-connection ⊊ product (in interaction, and inversely in transfer) Fusion: one domain, no interaction, everything transfers. E-connection: disjoint domains, one-way existential links, decidability transfers. Product: one grid, commuting relations, decidability generally fails. The E-connection sits exactly where the Fusion and Products entry says the space is unmapped, and it is the map — a construction with genuine interaction whose interaction is too weak to tile.

Why disjointness matters: undecidability of products comes from encoding tilings, which needs the two relations to address one plane. Disjoint domains mean there is no plane to address; the link relation goes from one universe to another and never returns to build a grid. That is the mechanism, and it is the same mechanism read in reverse.

Symbols.

Metatheory. E-connections are the answer to the question the fusion/product contrast poses. Fusion transfers everything because it says nothing; products say something and lose decidability; the interesting question was whether the trade is forced, and the answer is no — disjointness of domains buys interaction without a grid, and decidability transfers. That result is worth the entry on its own, but the sharper thing is the boundary: strengthening the link language to Booleans, inverses, or counting recovers undecidability, and the strengthenings that do so are exactly the ones that let a grid be forced. So the transfer/interaction trade is not a vague inverse proportion but a specific threshold, and the threshold is tiling. The abstract-description-system framework is what makes the theorem general — it applies to description logics, modal logics, and first-order fragments uniformly, so the result is about the construction rather than about any component.

Applies to. Combining description logics with spatial and temporal formalisms — the motivating case, and the one where products were known undecidable and fusions useless. Ontology integration, where two ontologies over different domains must be linked without merging. Spatio-temporal representation in AI. Modular knowledge representation, where the modules must stay separate and still refer to each other. The general question of how much interaction a combination can afford.

Limitations. The link operators are weak by design: a bare existential along E, with no counting, no inverses, and no Booleans on links, because each of those returns undecidability. Domains must be disjoint, which forbids the combinations where the same objects are described by both components — and that is a common case, not an exotic one. The transfer theorem's complexity bound is the maximum of the components plus an exponential, which is a good result and still an exponential. The construction is asymmetric in practice even when symmetric in definition, since the link relations are chosen with one direction in mind, and no canonical account says which links a given pair of components should have.

© 2026 Lingenic LLC