# A Description Logic for Analogical Reasoning

Steven Schockaert  Yazmín Ibáñez-García  Víctor Gutiérrez-Basulto Cardiff
University, UK
{schockaerts1,ibanezgarciay<EMAIL_ADDRESS>
###### Abstract

Ontologies formalise how the concepts from a given domain are interrelated.
Despite their clear potential as a backbone for explainable AI, existing
ontologies tend to be highly incomplete, which acts as a significant barrier
to their more widespread adoption. To mitigate this issue, we present a
mechanism to infer plausible missing knowledge, which relies on reasoning by
analogy. To the best of our knowledge, this is the first paper that studies
analogical reasoning within the setting of description logic ontologies. After
showing that the standard formalisation of analogical proportion has important
limitations in this setting, we introduce an alternative semantics based on
bijective mappings between sets of features. We then analyse the properties of
analogies under the proposed semantics, and show among others how it enables
two plausible inference patterns: rule translation and rule extrapolation.

##  1 Introduction

The last decade has witnessed an increasing interest in methods for automated
knowledge base completion. While most work has focused on predicting plausible
missing facts in knowledge graphs Bordes et al. (2013); Yang et al. (2015);
Trouillon et al. (2017); Balazevic et al. (2019), some authors have also
looked at the problem of predicting plausible missing rules in ontologies
Beltagy et al. (2013); Bouraoui and Schockaert (2019). The underlying
principle of these latter approaches is to rely on external knowledge about
the similarity structure of concepts, typically in the form of a vector space
embedding of concept names. The main idea is that knowledge about concepts can
often be extended to concepts with a similar representation in the given
vector space. The same principle also lies at the basis of rule-based
frameworks with a soft unification mechanism Medina et al. (2004); Rocktäschel
and Riedel (2017). However, these similarity based reasoning methods can
clearly only provide us with knowledge that is similar to what is already in
the knowledge base. Humans, on the other hand, can also infer plausible
knowledge in more creative ways, where a particularly prominent role is played
by the idea of reasoning by analogy. This phenomenon has been extensively
studied in cognitive science and philosophy Gentner (1983); Hofstadter et al.
(1995); Holyoak and Thagard (1997), but to the best of our knowledge, the use
of analogical reasoning for completing ontologies has not yet been
considered111We note that the term “analogical reasoning” has been used in the
literature to refer to a form of similarity-based ontology completion d’Amato
et al. (2006). In contrast, we reserve this term for methods that require
drawing parallels between different domains.

Within Artificial Intelligence, the formalisation of analogical reasoning
typically builds on analogical proportions, i.e. statements of the form “$A$
is to $B$ what $C$ is to $D$” Bayoudh et al. (2007); Prade and Richard (2014);
Barbot et al. (2019). A key result in this area has been the development of
analogical classifiers, which are based on the principle that whenever the
features of four examples are in an analogical proportion, then their class
labels should be in an analogical proportion as well Bayoudh et al. (2007);
Hug et al. (2016). The same principle can be applied to infer plausible
concept inclusions, i.e. concept inclusions which are not entailed from a
given TBox, but which are likely to hold given additional background knowledge
that we have about analogical relationships between different concepts. The
resulting inference pattern, which we call _rule extrapolation_ , is
illustrated in the next example.

######  Example 1 (Rule extrapolation).

Suppose we have an ontology with the following concept inclusions:

$\displaystyle\textit{Young}\sqcap\textit{Cat}$
$\displaystyle\sqsubseteq\textit{Cute}$ (1)
$\displaystyle\textit{Adult}\sqcap\textit{WildCat}$
$\displaystyle\sqsubseteq\textit{Dangerous}$ (2)
$\displaystyle\textit{Young}\sqcap\textit{Dog}$
$\displaystyle\sqsubseteq\textit{Cute}$ (3)

Suppose we are furthermore given that “ _Cat_ is to _WildCat_ what _Dog_ is to
_Wolf_ ”. Trivially, we also have that “ _Young_ is to _Adult_ what _Young_ is
to _Adult_ ” and “ _Cute_ is to _Dangerous_ what _Cute_ is to _Dangerous_ ”
Using rule extrapolation, we can then infer the following:

$\displaystyle\textit{Adult}\sqcap\textit{Wolf}$
$\displaystyle\sqsubseteq\textit{Dangerous}$ (4)

Analogies can also be used to infer plausible knowledge by allowing us to
transfer knowledge from one domain to another. This is illustrated in the
following example.

######  Example 2 (Rule translation).

Suppose we are given the following knowledge:

Program $\displaystyle\sqsubseteq\exists\textit{specifies}.\textit{Software}$
(5)

and the fact that “ _Program_ is to _Plan_ what _Software_ is to _Building”._
Then we can plausibly infer:

Plan $\displaystyle\sqsubseteq\exists\textit{specifies}.\textit{Building}$ (6)

Ontologies often use the same “templates” to encode knowledge from different
domains (e.g. knowledge about different professions). The strategy from
Example 2 then allows us to complete the ontology by introducing additional
domains.

Using analogies for identifying plausible missing knowledge is appealing,
because they can be learned from text quite effectively. For instance, Turney
Turney (2006) proposed a method for identifying similarities between pairs of
words (i.e. analogical proportions) using matrix factorization and ternary co-
occurrence statistics, which approximated the performance of an average US
college applicant. Moreover, the GPT-3 language model is able to identify
analogical word pairs with even higher accuracy Brown et al. (2020). To a more
limited extent, some types of analogical relationships can also be obtained
from word embeddings Mikolov et al. (2013).

The main aim of this paper is to propose a semantics for modelling analogies
within the setting of description logics, which introduces a number of unique
challenges (see Section 3). We focus in particular on an extension of ${\cal
EL}_{\bot}$. We start from the semantics proposed by Ibáñez-García et al.
Ibáñez-García et al. (2020), which extends the ${\cal EL}$ semantics by
assigning to each individual a set of features. Their aim was to support
another form of plausible inference, called interpolation (see Section 2). We
show that having access to these features in the semantics also allows us to
formalise analogies.

##  2 Background

We start by introducing the Description Logic (DL) ${\cal
EL}_{\bot}^{\bowtie}$, which is a straightforward extension of the logic
${\cal EL}^{\bowtie}$ that was proposed in Ibáñez-García et al. (2020) to
formalise _rule interpolation_ 222We include $\bot$ because disjointness will
play an important role in this paper.. Our approach to analogical reasoning in
this paper will build on ${\cal EL}_{\bot}^{\bowtie}$. Rule interpolation is
another inference pattern for obtaining plausible missing concept inclusions
in a DL ontology. Interpolation is based on the notion of _betweenness_ ,
where a concept $B$ is said to be between concepts $A$ and $C$ if $B$ has all
the natural properties that $A$ and $C$ have in common. In such a case,
knowledge that holds for both $A$ and $C$ seems likely to hold for $B$ as
well. This inference pattern is illustrated in the next example.

######  Example 3 (Rule interpolation).

Suppose we have the following concept inclusions:

Cat $\displaystyle\sqsubseteq X$ Wolf $\displaystyle\sqsubseteq X$ (7)

As long as $X$ is a “natural concept”, it seems plausible that the following
concept inclusion also holds:

$\textit{Dog}\sqsubseteq X$

This is because all the common (natural) properties of Cat and Wolf are also
satisfied by Dog. In such a case, we say that the concept Dog is _between_ the
concepts Cat and Wolf.

The notion of naturalness plays an important role in most philosophical
accounts of induction. Intuitively speaking, a natural concept or property is
one that admits inductive inferences. The semantics from Ibáñez-García et al.
(2020) is based on the common view that natural concepts are those which can
be characterised as a set of features (i.e. a conjunction of elementary
properties) Tversky (1977).

Syntax. The logic ${\cal EL}_{\bot}^{\bowtie}$ extends the standard DL ${\cal
EL}_{\bot}$ with _in-between concepts_ of the form
$C{\,\mathbin{\bowtie}\,}D$, describing the set of objects that are between
the concepts $C$ and $D$. Further, ${\cal EL}_{\bot}^{\bowtie}$ includes an
infinite set of _natural concept names_. More precisely, consider countably
infinite but disjoint sets of _concept names_ $\mathsf{N_{C}}$ and _role
names_ $\mathsf{N_{R}}$, where $\mathsf{N_{C}}$ contains a distinguished
infinite set of _natural concept names_ $\mathsf{N^{Nat}_{C}}$. The syntax of
_${\cal EL}_{\bot}^{\,\mathbin{\bowtie}\,}$ concepts $C,D$_ is defined by the
following grammar, where $A\in\mathsf{N_{C}}$,
$A^{\prime}\in\mathsf{N^{Nat}_{C}}$ and $r\in\mathsf{N_{R}}$:

$\displaystyle C,D$ $\displaystyle:=\top\mid\bot\mid A\mid C\sqcap
D\mid\exists r.C\mid N$ $\displaystyle N,N^{\prime}$
$\displaystyle:=A^{\prime}\mid N\sqcap N^{\prime}\mid
N{\,\mathbin{\bowtie}\,}N^{\prime}$

Concepts of the form $N,N^{\prime}$ are called _natural concepts_. An _${\cal
EL}_{\bot}^{\,\mathbin{\bowtie}\,}$ TBox_ is a finite set of concept
inclusions $C\sqsubseteq D$, where $C,D$ are ${\cal
EL}_{\bot}^{\,\mathbin{\bowtie}\,}$ concepts.

Semantics. The semantics of ${\cal EL}_{\bot}^{\bowtie}$ is given in terms of
feature-enriched interpretations, which extend standard first-order
interpretations by also specifying a mapping $\pi$ from individuals to sets of
_features_. Formally, a _feature-enriched_ interpretation is a tuple
$\mathfrak{I}=(\mathcal{I},\mathcal{F},\pi)$ in which
$\mathcal{I}=(\Delta^{\mathcal{I}},\cdot^{\mathcal{I}})$ is a classical DL
interpretation, $\mathcal{F}$ is a finite set of features, and
$\pi:\Delta^{\mathcal{I}}\rightarrow 2^{\mathcal{F}}$, such that the following
hold:

  1. 1.

For each $d\in\Delta^{\mathcal{I}}$ it holds that $\pi(d)\subset\mathcal{F}$;

  2. 2.

for each $F\subset\mathcal{F}$ there exists some individual
$d\in\Delta^{\mathcal{I}}$ such that $\pi(d)=F$.

For an ${\cal EL}_{\bot}^{\bowtie}$ concept $C$, $C^{\mathfrak{I}}$ is defined
as a pair $\langle C^{\mathcal{I}},\varphi(C)\rangle$ where
$C^{\mathcal{I}}\subseteq\Delta^{\mathcal{I}}$ and $\varphi(C)$ is the set of
all features associated with a concept $C$, defined as:

$\varphi(C)=\bigcap\\{\pi(d)\mid d\in C^{\mathcal{I}}\\}$

Intuitively, the set of features $\varphi(C)$ describes the concept $C$ at a
finer-grained level that what may be possible in the language. This makes it
possible to capture knowledge about what different concepts have in common,
which is needed in ${\cal EL}_{\bot}^{\bowtie}$ to model the semantics of in-
between concepts.

For a standard ${\cal EL}_{\bot}$ concept $C$, $C^{\mathcal{I}}$ is defined as
usual Baader et al. (2017). For in-between concepts, $\cdot^{\mathcal{I}}$ is
defined as follows.

$(N{\,\mathbin{\bowtie}\,}N^{\prime})^{\mathcal{I}}=\\{d\in\Delta^{\mathcal{I}}\mid\varphi(N)\cap\varphi(N^{\prime})\subseteq\pi(d)\\}.$

Intuitively, $(N{\,\mathbin{\bowtie}\,}N^{\prime})^{\mathcal{I}}$ contains all
elements from the domain that have all the features that are common to both
$N$ and $N^{\prime}$. A feature-enriched interpretation
$\mathfrak{I}=(\mathcal{I},\mathcal{F},\pi)$ _satisfies_ a concept inclusion
$C\sqsubseteq D$ if $C^{\mathcal{I}}\subseteq D^{\mathcal{I}}$. $\mathfrak{I}$
is a _model_ of an ${\cal EL}^{\,\mathbin{\bowtie}\,}$ TBox $\mathcal{T}$ if
it satisfies all CIs in $\mathcal{T}$ and for every natural concept $N$ in
$\mathcal{T}$, it holds that

$\displaystyle
N^{\mathcal{I}}=\\{d\in\Delta^{\mathcal{I}}\,|\,\varphi(N)\subseteq\pi(d)\\}$
(8)

i.e. $N$ is fully specified by its features. It is easy to verify that (8) is
satisfied for a complex natural concept, as soon as it is satisfied for its
constituent natural concept names. A concept $C$ _is satisfiable w.r.t. a TBox
$\mathcal{T}$_, if there is a model $\mathfrak{I}$ of $\mathcal{T}$ such that
$C^{\mathfrak{I}}\neq\langle\emptyset,\mathcal{F}\rangle$.

The purpose of introducing features in the semantics of ${\cal
EL}_{\bot}^{\bowtie}$ is to make explicit what different concepts have in
common, and to use this as the basis for enabling a particular kind of
inductive inference (i.e. interpolation). For instance, in the case of Example
3, if the concept inclusions in (7) are complemented with
$\textit{Dog}\sqsubseteq\textit{Cat}\bowtie\textit{Wolf}$, it can be verified
that $\textit{Dog}\sqsubseteq X$ can indeed be inferred (assuming all concept
names are natural). In applications, knowledge about in-between concepts would
typically be induced from a vector space embedding. See, for instance,
Bouraoui and Schockaert (2019) for a practical application of rule
interpolation based on pre-trained word embeddings. In this paper, we will
build on the feature-enriched semantics to encode correspondences between
analogous domains.

##  3 Analogical Concepts

Analogical proportions are a central notion in the formalisation of analogical
reasoning, going back to Aristotle (see Barbot et al. (2019) for a historical
perspective). While they can be defined more generally, here we will focus on
analogical proportions between sets. In particular, the sets
$S_{1},S_{2},S_{3},S_{4}$ are said to be in an analogical proportion, denoted
as $S_{1}{:}S_{2}\,{::}\,S_{3}{:}S_{4}$ if $S_{1}$ and $S_{2}$ differ in the
same way that $S_{3}$ and $S_{4}$ differ. Formally,
$S_{1}{:}S_{2}\,{::}\,S_{3}{:}S_{4}$ is satisfied if:

$\displaystyle S_{1}\setminus S_{2}$ $\displaystyle=S_{3}\setminus S_{4}$
$\displaystyle S_{2}\setminus S_{1}$ $\displaystyle=S_{4}\setminus S_{3}$ (9)

Some key properties of analogical proportions are as follows:

Reflexivity

$A{:}B\,{::}\,A{:}B$

Symmetry

$(A{:}B\,{::}\,C{:}D)\Leftrightarrow(C{:}D\,{::}\,A{:}B)$

Exchange of means

$(A{:}B\,{::}\,C{:}D)\Leftrightarrow(A{:}C\,{::}\,B{:}D)$

S-transitivity

$(A{:}B\,{::}\,C{:}D){\wedge}(A{:}B\,{::}\,E{:}F){\Rightarrow}(C{:}D\,{::}\,E{:}F)$

C-transitivity

$(A{:}C\,{::}\,D{:}B){\wedge}(A{:}E\,{::}\,F{:}B){\Rightarrow}(C{:}E\,{::}\,F{:}D)$

###  3.1 Analogical Proportions between DL Concepts

In this paper, we are concerned with analogies between description logic
concepts. We can define analogical proportions between ${\cal
EL}_{\bot}^{\bowtie}$ concepts $A,B,C,D$ as
$A^{\mathcal{I}}{:}B^{\mathcal{I}}\,{::}\,C^{\mathcal{I}}{:}D^{\mathcal{I}}$
or as $\varphi(A){:}\varphi(B)\,{::}\,\varphi(C){:}\varphi(D)$. In general
these two expressions are not equivalent, and there are advantages in
requiring that both of them are satisfied at the same time, which has been
studied in detail in Barbot et al. (2019) within the setting of Formal Concept
Analysis. However, if $A,B,C,D$ are natural, then
$A^{\mathcal{I}}{:}B^{\mathcal{I}}\,{::}\,C^{\mathcal{I}}{:}D^{\mathcal{I}}$
and $\varphi(A){:}\varphi(B)\,{::}\,\varphi(C){:}\varphi(D)$ are equivalent.
Moreover, for natural concepts, the semantic constraint
$\varphi(A){:}\varphi(B)\,{::}\,\varphi(C){:}\varphi(D)$ can be modelled
syntactically in ${\cal EL}_{\bot}^{\bowtie}$. Indeed it holds that
$\varphi(A){:}\varphi(B)\,{::}\,\varphi(C){:}\varphi(D)$ is satisfied iff the
following conditions are satisfied333This follows immediately from the
characterisation of Boolean analogical proportions in terms of conjunction and
disjunction; see Prade and Richard (2013) for details.:

$\displaystyle\varphi(A)\cap\varphi(D)$
$\displaystyle=\varphi(B)\cap\varphi(C)$ (10)
$\displaystyle\varphi(A)\cup\varphi(D)$
$\displaystyle=\varphi(B)\cup\varphi(C)$ (11)

The analogical proportion
$\varphi(A){:}\varphi(B)\,{::}\,\varphi(C){:}\varphi(D)$ is thus satisfied if
the following concept inclusions are satisfied:

$\displaystyle A\sqcap D$ $\displaystyle\sqsubseteq B\sqcap C$ $\displaystyle
B\sqcap C$ $\displaystyle\sqsubseteq A\sqcap D$ $\displaystyle A\bowtie D$
$\displaystyle\sqsubseteq B\bowtie C$ $\displaystyle B\bowtie C$
$\displaystyle\sqsubseteq A\bowtie D$

In the following, we will write $A{:}B\,{::}\,C{:}D$ as an abbreviation for
these four concept inclusions. The fact that we can model $A{:}B\,{::}\,C{:}D$
within ${\cal EL}_{\bot}^{\bowtie}$ is an advantage, but as we will see below,
modelling analogies between DL concepts in this way has a number of important
limitations.

###  3.2 Desiderata for Modelling Analogies in DLs

Our motivation for studying analogies is to enable plausible inferences. A
clear requirement is thus that we want some form of the _rule extrapolation_
and _rule translation_ inference patterns, as illustrated in Examples 1 and 2,
to be satisfied. Another important requirement comes from the fact that we
usually only have access to information about analogical relationships between
concept names (e.g. obtained from a language model). However, the
aforementioned inference pattern may rely on analogical relationships between
complex concepts. To enable non-trivial inferences in practice, it is thus
important that analogies between concept names can be _lifted_ to analogies
between complex concepts.

Let us now consider the suitability of analogical proportions, in light of
these desiderata. First, rule translation is satisfied for analogical
proportions.

######  Proposition 1.

Let $\mathfrak{I}=(\mathcal{I},\mathcal{F},\pi)$ be a feature-enriched
interpretation, and let $A_{1},A_{2},B_{1},B_{2}$ be natural concepts in
$\mathfrak{I}$. If
$\varphi(A_{1}){:}\varphi(A_{2})\,{::}\,\varphi(B_{1}){:}\varphi(B_{2})$ holds
and $\mathfrak{I}$ satisfies $A_{1}\sqsubseteq B_{1}$, then $\mathfrak{I}$
also satisfies $A_{2}\sqsubseteq B_{2}$.

However, rule extrapolation is not valid for analogical proportions.
Furthermore, analogical proportions between concept names cannot be lifted to
complex concepts. For instance, from $A_{1}{:}B_{1}\,{::}\,C_{1}{:}D_{1}$ and
$A_{2}{:}B_{2}\,{::}\,C_{2}{:}D_{2}$, in general we cannot infer $(A_{1}\sqcap
A_{2}){:}(B_{1}\sqcap B_{2})\,{::}\,(C_{1}\sqcap C_{2}){:}(D_{1}\sqcap
D_{2})$. Counterexamples are provided in the appendix.

##  4 The Logic ${\cal EL}_{\bot}^{\textit{ana}}$

Given the limitations of analogical proportions that were highlighted in
Section 3.2, we propose an alternative approach for modelling analogies
between description logic concepts. This approach is based on the common view
that analogies are mappings from one domain into another, which lies among
others at the basis of the seminal Structure Mapping framework Gentner (1983).
In particular, we propose the logic ${\cal EL}_{\bot}^{\textit{ana}}$, which
extends ${\cal EL}_{\bot}^{\bowtie}$ with two novel elements: analogy
assertions and intra-domain roles. Analogy assertions are similar to
analogical proportions, in that they encode a relationship of the form “$A$ is
to $B$ what $C$ is to $D$”, but their semantics is defined in terms of
mappings between different domains, where domains will be identified with sets
of features. Intuitively, intra-domain roles are roles which preserve the
structure of analogous domains.

###  4.1 Syntax

Let $\mathsf{N_{C}}$, $\mathsf{N^{Nat}_{C}}$ and $\mathsf{N_{R}}$ be defined
as before. We assume that $\mathsf{N_{R}}$ contains an infinite set
$\mathsf{N^{\textit{Int}}_{R}}$ of distinguished _intra-domain role names_.
The syntax of ${\cal EL}^{\textit{ana}}_{\bot}$ concepts $C,D$ is defined by
the following grammar, where $A\in\mathsf{N_{C}}$,
$A^{\prime}\in\mathsf{N^{Nat}_{C}}$, $r\in\mathsf{N_{R}}$ and
$r^{\prime}\in\mathsf{N_{R}^{\textit{Int}}}$:

$\displaystyle C,D$ $\displaystyle:=\top\mid\bot\mid A\mid C\sqcap
D\mid\exists r.C\mid N$ $\displaystyle N,N^{\prime}$
$\displaystyle:=A^{\prime}\mid N\sqcap N^{\prime}\mid
N{\,\mathbin{\bowtie}\,}N^{\prime}\mid\exists r^{\prime}.N$

${\cal EL}_{\bot}^{\textit{ana}}$ concepts extend ${\cal EL}_{\bot}^{\bowtie}$
concepts by allowing existential restrictions over intra-domain roles as
natural concepts. An ${\cal EL}^{\textit{ana}}_{\bot}$ TBox is a finite set
containing two types of assertions: (i) ${\cal EL}^{\textit{ana}}_{\bot}$
concept inclusions, and (ii) _analogy assertions_ of the form
$C_{1}{\triangleright}D_{1}{::}C_{2}{\triangleright}D_{2}$, where
$C_{1},C_{2},D_{1},D_{2}$ are natural ${\cal EL}^{\textit{ana}}_{\bot}$
concepts.

###  4.2 Semantics

Analogies intuitively involve transferring knowledge from one domain to
another domain444In this paper, we use the term domain to refer to a
particular thematic area. This should not be confused with the set
$\Delta^{\mathcal{I}}$, which is often referred to as the domain of the
interpretation $\mathcal{I}$., e.g. from software engineering to architecture
in the case of Example 2. In our framework, these domains will be associated
with subsets of $\mathcal{F}$. In particular, we will require that
interpretations specify a partition $[\mathcal{F}_{1},...,\mathcal{F}_{k}]$ of
$\mathcal{F}$, defining the different domains of interest. Some of the
partition classes will furthermore be viewed as being analogous, in the sense
that there is some kind of structure-preserving mapping between them.

Another extension of the feature-enriched semantics is aimed at improving how
disjointess can be modelled. In the semantics from Ibáñez-García et al.
(2020), no individual $d\in\Delta^{\mathcal{I}}$ is allowed to have all the
features from $\mathcal{F}$, but all proper subsets $F\subset\mathcal{F}$ are
witnessed in the sense that there is some $d$ such that $\pi(d)=F$. This
limits how disjoint concepts can be modelled. For instance, $B$ cannot be
satisfied w.r.t. $\\{B\sqsubseteq A\bowtie C,A\sqcap B\sqsubseteq\bot,A\sqcap
C\sqsubseteq\bot,B\sqcap C\sqsubseteq\bot\\}$ using a feature-enriched
interpretation. Disjointness will play an important role in our semantics, as
concepts from different domains will be required to be disjoint (see below).
For this reason, we extend the feature-enriched semantics with sets of
_forbidden feature combinations_. In particular, interpretations will specify
a set $\mathcal{X}\in 2^{\mathcal{F}}$ such that for $X\in\mathcal{X}$, it
holds that no individual can have all the features from $X$. For the ease of
presentation, we write $\mathcal{C}$ for the set of all _consistent sets of
features_ , i.e. $F\in\mathcal{C}$ iff $F\not\supseteq X$ for all
$X\in\mathcal{X}$. We also write $\mathcal{C}^{i}$ for the restriction of
$\mathcal{C}$ to subsets of $\mathcal{F}_{i}$.

######  Definition 1.

Let $[\mathcal{F}_{1},...,\mathcal{F}_{k}]$ be a partition of a non-empty
finite set $\mathcal{F}$. We call
$\mathfrak{I}=(\mathcal{I},[\mathcal{F}_{1},...,\mathcal{F}_{k}],\mathcal{X},\pi,\sim,\mathcal{S})$
a _domain constrained interpretation_ if
$\mathcal{I}=(\Delta^{\mathcal{I}},.^{\mathcal{I}})$ is a classical DL
interpretation, $\mathcal{X}\subseteq 2^{\mathcal{F}}$,
$\mathcal{F}\in\mathcal{X}$, $\pi:\Delta^{\mathcal{I}}\rightarrow
2^{\mathcal{F}}$, $\sim$ is an equivalence relation over $\\{1,...,k\\}$ and
$S=\\{\sigma_{(s,t)}\,|\,(s,t)\in\sim\\}$, with each $\sigma_{s,t}$ a
bijection from $\mathcal{F}_{s}$ to $\mathcal{F}_{t}$, and we have:

  1. 1.

for every $d\in\Delta^{\mathcal{I}}$ and $X\in\mathcal{X}$ it holds that
$X\not\subseteq\pi(d)$;

  2. 2.

if $X\in\mathcal{C}$ then $\pi(d)=X$ for some $d\in\Delta^{\mathcal{I}}$;

  3. 3.

we have $\sigma_{(s,t)}^{-1}=\sigma_{(t,s)}$ and
$\sigma_{(t,u)}\circ\sigma_{(s,t)}=\sigma_{(s,u)}$ for any
$(s,t),(t,u)\in\sim$;

  4. 4.

for $F\in\mathcal{C}^{i}$ and $(i,j)\in\sim$, we have
$\\{\sigma_{(i,j)}(f)\,|\,f\in F\\}\in\mathcal{C}$;

  5. 5.

if $f\in\mathcal{F}_{i}\text{ and }g\in\mathcal{F}_{j}\text{ then
}\\{f,g\\}\in\mathcal{X}$, for all $(i,j)\in\sim$ with $i\neq j$.

Intuitively, each of the sets $\mathcal{F}_{i}$ corresponds to a different
domain. If $(s,t)\in\sim$, it means that there is an analogy between the
_source domain_ $\mathcal{F}_{s}$ and _the target domain_ $\mathcal{F}_{t}$.
In that case, there is a one-to-one mapping $\sigma_{(s,t)}$ between the
features from $\mathcal{F}_{s}$ and those from $\mathcal{F}_{t}$. The first
two conditions from Definition 1 capture the fact that a set of features
$X\subseteq\mathcal{F}$ is witnessed by some individual iff it is consistent,
i.e. $X\in\mathcal{C}$. The third condition ensures that the mappings
$\sigma_{(i,j)}$ can be composed and reversed. The fourth condition encodes
that the mapping $\sigma_{(i,j)}$ maps consistent feature combinations to
consistent feature combinations. This is a natural requirement, given the
intuition that analogous domains should have the same structure. The last
condition captures the requirement that individuals cannot have features from
two analogous domains. While analogies are normally indeed defined between
distinct domains, the reader may wonder at this point whether this restriction
is necessary. We will come back to this question in Section 4.4.

#### Domain Translations

Before presenting the semantics of analogy assertions, we first study how the
bijections $\sigma_{(i,j)}$ can be combined to define mappings between the
sets of features $\varphi(C),\varphi(D)$ associated with two concepts. First,
we define a _domain assignment mapping_ $\delta$, which maps each concept $C$
to the set of domains on which it depends:

$\delta(C)=\\{i\mid\mathcal{F}_{i}\cap\varphi(C)\neq\emptyset\\}$

Next, we extend the mappings $\sigma_{(i,j)}$ to mappings between sets of
domains. Let $U=\\{(s_{1},t_{1}),\ldots,(s_{l},t_{l})\\}$, with
$s_{1},\ldots,s_{l}$ all distinct and $t_{1},\ldots,t_{l}$ all distinct. The
mapping $\sigma_{U}$ is defined as follows:

$\displaystyle\sigma_{U}(f)=\begin{cases}\sigma_{(s_{i},t_{i})}(f)&\text{if
$f\in\mathcal{F}_{s_{i}}$}\\\ f&\text{otherwise}\end{cases}$

We call $\sigma_{U}$ a _domain translation_ , and write $\textit{src}(U)$ for
the set $\\{s_{1},\ldots,s_{l}\\}$ of source domains and $\textit{tgt}(U)$ for
the set $\\{t_{1},\ldots,t_{l}\\}$ of target domains. The source domains need
to be distinct to ensure that the domain translation is uniquely defined.
Target domains are required to be distinct to allow domain translations to be
reversible. For the ease of presentation, we will write $\sigma_{U}(F)$ to
denote the set $\\{\sigma_{U}(f)\,|\,f\in F\\}$.

For a pair of concepts $C$ and $D$, we write $\mu(C,D)$ for the set of domain
translations $\sigma_{U}$ such that:

$\displaystyle\varphi(D)$ $\displaystyle=\sigma_{U}(\varphi(C))$ (12)
$\displaystyle\textit{src}(U)$ $\displaystyle\subseteq\delta(C)$ (13)
$\displaystyle\textit{tgt}(U)\cap(\delta(C)\setminus\textit{src}(U))$
$\displaystyle=\emptyset$ (14)

The first condition states that the domain translations in $\mu(C,D)$
essentially “translate” the concept $C$ to the concept $D$. The second
condition ensures that $\mu(C,D)$ contains minimal domain translations only,
in the sense that $U$ should not contain any redundant pairs. The third
condition is needed to ensure that domain translations are reversible. To see
why this is needed, let $\varphi(C)=\\{f_{1},g_{2}\\}$,
$\varphi(D)=\\{g_{1},g_{2}\\}$, $\mathcal{F}_{1}=\\{f_{1},f_{2}\\}$,
$\mathcal{F}_{2}=\\{g_{1},g_{2}\\}$, $\sigma_{(1,2)}(f_{i})=g_{i}$. Then
$\varphi(D)=\sigma_{(1,2)}(\varphi(C))$, but there is no domain translation
$\sigma_{U}$ s.t. $\varphi(C)=\sigma_{U}(\varphi(D))$. As the following result
shows, imposing (14) is enough to ensure reversibility.

######  Proposition 2.

Let $U$ be a domain translation, and let
$U^{\smallsmile}=\\{(t,s)\,|\,(s,t)\in U\\}$. It holds that
$\sigma^{-1}_{U}=\sigma_{U^{\smallsmile}}$.

As the next result shows, the composition of two domain translations is also a
valid domain translation. In particular, if there is some domain translation
$\sigma_{U}$ that maps $C$ to $D$ and some domain translation $\sigma_{V}$
that maps $D$ to $E$, then $\sigma_{U}$ and $\sigma_{V}$ can be composed to
define a domain translation from $C$ to $E$. Moreover, in such a case, any
domain translation from $C$ to $E$ can be defined as such a composition.

######  Proposition 3.

If $\mu(C,D)\neq\emptyset$ and $\mu(D,E)\neq\emptyset$ we have:

$\mu(C,E)=\\{\sigma_{U\oplus
V}\,|\,\sigma_{U}\in\mu(C,D),\sigma_{V}\in\mu(D,E)\\}$

where

$\displaystyle U\oplus V=$ $\displaystyle\\{(i,k)\,|\,(i,j)\in U,(j,k)\in
V,i\neq k\\}$ $\displaystyle\cup\\{(i,j)\,|\,(i,j)\in
U,j\notin\textit{src}(V)\\}$ $\displaystyle\cup\\{(j,k)\,|\,(j,k)\in
V,j\notin\textit{tgt}(U)\\}$

#### Semantics of Intra-Domain Roles

We will need to put additional constraints on the interpretation of a role $r$
to be able to infer $(\exists r.A){\triangleright}(\exists r.B){::}(\exists
r.C){\triangleright}(\exists r.D)$ or $A{\triangleright}B{::}(\exists
r.C){\triangleright}(\exists r.D)$ from
$A{\triangleright}B{::}C{\triangleright}D$. To allow such lifting of analogy
assertions, we will associate with each intra-domain role $r$ a mapping
$\kappa_{r}$ between sets of features, which satisfies a number of conditions.
In particular, we introduce the following notion of intra-domain relation.

######  Definition 2.

Let
$\mathfrak{I}=(\mathcal{I},[\mathcal{F}_{1},...,\mathcal{F}_{k}],\mathcal{X},\pi,\sim,\mathcal{S})$
be a domain constrained interpretation and let $r\in\mathsf{N_{R}}$. We say
that $r$ is _interpreted as an intra-domain relation_ if for every concept
$C$, we have $(\exists
r.C)^{\mathcal{I}}=\\{d\in\Delta^{\mathcal{I}}\,|\,\pi(d)\supseteq\kappa_{r}(\varphi(C)\\}$,
for a mapping $\kappa_{r}$ satisfying:

  1. 1.

$\kappa_{r}(F)=\kappa_{r}(F\cap\mathcal{F}_{1})\cup...\cup\kappa_{r}(F\cap\mathcal{F}_{k})$,
for all $F\in\mathcal{C}$;

  2. 2.

$\kappa_{r}(F)\subseteq\mathcal{F}_{i}$, for all $i\in\\{1,...,k\\}$ and
$F\in\mathcal{C}^{i}$;

  3. 3.

$\kappa_{r}(\sigma_{\\{(i,j)\\}}(F))=\sigma_{\\{(i,j)\\}}(\kappa_{r}(F))$, for
all $(i,j)\in\sim$ and $F\in\mathcal{C}^{i}$;

  4. 4.

$\kappa_{r}(F)\neq\emptyset$, for all $i\in\\{1,...,k\\}$ and
$F\in\mathcal{C}^{i}\setminus\\{\emptyset\\}$.

The first two conditions in Definition 2 state that the features in
$\kappa_{r}(F)$ are determined per domain. The third condition captures the
intuition that analogous domains should have the same structure. The last
condition essentially encodes that whenever $C$ depends on some domain $i$
then $\exists r.C$ should also depend on domain $i$, i.e. if $\varphi(C)$
contains at least one feature from $\mathcal{F}_{i}$ then the same should be
true for $\kappa_{r}(\varphi(C))$. Note that if $r$ is interpreted as an
intra-domain relation and $C$ is a natural concept, then $\exists r.C$ is a
natural concept, whose features are determined by the features in
$\varphi(C)$. We then have $\varphi(\exists r.C)=\kappa_{r}(\varphi(C))$.

The semantics of ${\cal EL}_{\bot}^{\textit{ana}}$ concepts can now be defined
similarly to Section 2, but we additionally require that every
$r\in\mathsf{N_{R}^{\textit{Int}}}$ is interpreted as an intra-domain
relation.

#### Semantics of TBoxes

We now define the semantics of ${\cal EL}^{\textit{ana}}_{\bot}$ TBoxes. We
start with that of analogy assertions. We say that _a domain constrained
interpretation $\mathfrak{I}$ satisfies the analogy assertion
$C_{1}{\triangleright}C_{2}{::}D_{1}{\triangleright}D_{2}$_ if:

$\displaystyle\mu(C_{1},C_{2})\cap\mu(D_{1},D_{2})$
$\displaystyle\neq\emptyset$ (15)

Clearly, $C_{1}{\triangleright}C_{2}{::}D_{1}{\triangleright}D_{2}$ is
equivalent to $D_{1}{\triangleright}D_{2}{::}C_{1}{\triangleright}C_{2}$. One
may wonder whether (15) is sufficient, i.e. whether we should not require
$\mu(C_{1},C_{2})=\mu(D_{1},D_{2})$. However, as the following result shows,
for non-empty concepts, $\mu(C_{1},C_{2})$ and $\mu(D_{1},D_{2})$ can have at
most one element.

######  Proposition 4.

Let $\mathfrak{I}=(\mathcal{I},\mathcal{F},\mathcal{X},\pi,\sim,\mathcal{S})$
be a domain-constrained interpretation. If $C^{\mathcal{I}}\neq\emptyset$,
$D^{\mathcal{I}}\neq\emptyset$ and $\mu(C,D)\neq\emptyset$, then
$|\mu(C,D)|=1$.

We define the semantics of ${\cal EL}^{\textit{ana}}_{\bot}$ TBoxes similarly
to Section 2, but now including analogy assertions. A domain constrained
interpretation _$\mathfrak{I}$ is a model of an ${\cal
EL}^{\textit{ana}}_{\bot}$ TBox $\mathcal{T}$_ if $\mathfrak{I}$ satisfies all
CIs and analogy assertions in $\mathcal{T}$; every natural concept
$N\in\mathcal{T}$ is fully specified by its features; and every intra-domain
role is interpreted as an intra-domain relation. For a TBox $\mathcal{T}$ and
CI or analogy assertion $\phi$ we write $\mathcal{T}\models\phi$ to denote
that every model of $\mathcal{T}$ satisfies $\phi$. If $\mathcal{T}$ is a
singleton of the form $\\{\psi\\}$, we also write this as $\psi\models\phi$.

###  4.3 Properties of Analogy Assertions

#### Basic Properties

Before returning to the desiderata from Section 3.2, we briefly look at the
properties of analogical proportions that were listed in Section 3. First,
reflexivity is trivially satisfied. The symmetry property also holds for
analogy assertions, thanks to the reversibility of domain translations.

######  Proposition 5.

We have $C_{1}{\triangleright}C_{2}{::}D_{1}{\triangleright}D_{2}\models
C_{2}{\triangleright}C_{1}{::}D_{2}{\triangleright}D_{1}$.

Exchange of means is not satisfied. This can easily be seen from the fact that
whenever $C_{1}{\triangleright}C_{2}{::}D_{1}{\triangleright}D_{2}$ is
satisfied, we have $|\varphi(C_{1})|=|\varphi(C_{2})|$ and
$|\varphi(D_{1})|=|\varphi(D_{2})|$ but not necessarily
$|\varphi(C_{1})|=|\varphi(D_{1})|$. As a result of this, there are two
variants of S-transitivity that can be considered. As the next proposition
shows, both of these variants are satisfied.

######  Proposition 6.

It holds that:

$\displaystyle\\{C_{1}{\triangleright}C_{2}{::}D_{1}{\triangleright}D_{2},D_{1}{\triangleright}D_{2}{::}E_{1}{\triangleright}E_{2}\\}$
$\displaystyle{\models}C_{1}{\triangleright}C_{2}{::}E_{1}{\triangleright}E_{2}$
(16)
$\displaystyle\\{C_{1}{\triangleright}C_{2}{::}D_{1}{\triangleright}D_{2},C_{2}{\triangleright}C_{3}{::}D_{2}{\triangleright}D_{3}\\}$
$\displaystyle{\models}C_{1}{\triangleright}C_{3}{::}D_{1}{\triangleright}D_{3}$
(17)

We also have that $C$-transitivity is satisfied.

######  Proposition 7.

It holds that:

$\displaystyle\\{C_{1}{\triangleright}D_{1}{::}D_{2}{\triangleright}C_{2},C_{1}{\triangleright}E_{1}{::}E_{2}{\triangleright}C_{2}\\}$
$\displaystyle\models
D_{1}{\triangleright}E_{1}{::}E_{2}{\triangleright}D_{2}$

#### Lifting analogy assertions

As the next two results show, analogy assertions can indeed be lifted to (non-
empty) conjunctions and existentially quantified concepts.

######  Proposition 8.

Let
$\mathfrak{I}=(\mathcal{I},[\mathcal{F}_{1},...,\mathcal{F}_{k}],\mathcal{X},\pi,\sim,\mathcal{S})$
be a domain-constrained interpretation satisfying
$(C_{i}{\sqcap}D_{i})^{\mathcal{I}}\neq\emptyset$ for $i{\in}\\{1..4\\}$,
$C_{1}{\triangleright}C_{2}{::}C_{3}{\triangleright}C_{4}$ and
$D_{1}{\triangleright}D_{2}{::}D_{3}{\triangleright}D_{4}$. Then
$\mathfrak{I}$ also satisfies $(C_{1}\sqcap D_{1}){\triangleright}(C_{2}\sqcap
D_{2}){::}(C_{3}\sqcap D_{3}){\triangleright}(C_{4}\sqcap D_{4})$.

######  Proposition 9.

Let $r$ be an intra-domain role. It holds that:

$\displaystyle C{\triangleright}D{::}E{\triangleright}F$
$\displaystyle\models(\exists r.C){\triangleright}(\exists r.D){::}(\exists
r.E){\triangleright}(\exists r.F)$ (18) $\displaystyle
C{\triangleright}D{::}E{\triangleright}F$ $\displaystyle\models
C{\triangleright}D{::}(\exists r.E){\triangleright}(\exists r.F)$ (19)

#### Analogy Based Inference Patterns

We now return to the two considered analogy based inference patterns: rule
translation and rule extrapolation. First, similar as for analogical
proportions, we find that rule translation is supported.

######  Proposition 10.

Let $\mathfrak{I}$ be a domain constrained interpretation. If $\mathfrak{I}$
satisfies
$\\{C_{1}{\triangleright}D_{1}{::}C_{2}{\triangleright}D_{2},C_{1}\sqsubseteq
C_{2}\\}$ then $\mathfrak{I}$ also satisfies $D_{1}\sqsubseteq D_{2}$.

######  Example 4.

Suppose
$\textit{Program}\,{\triangleright}\textit{Plan}{::}\textit{Software}\,{\triangleright}\textit{Building}$
holds and assume that specifies is an intra-domain role. Using Proposition 9
we can then infer:

$\textit{Program}\,{\triangleright}\textit{Plan}{::}(\exists\textit{specifies}.\textit{Software}){\triangleright}(\exists\textit{specifies}.\textit{Building})$

If we are additionally given that the concept inclusion (5) is satisfied, we
can infer (6) using Proposition 10.

A version of rule extrapolation is also supported.

######  Proposition 11.

Let
$\mathfrak{I}=(\mathcal{I},[\mathcal{F}_{1},...,\mathcal{F}_{k}],\mathcal{X},\pi,\sim,\mathcal{S})$
be a domain constrained interpretation. Suppose that
$C_{1}^{\mathcal{I}}\neq\emptyset$ and that $\mathfrak{I}$ satisfies the
following TBox:

$\displaystyle\mathcal{T}=\\{$ $\displaystyle
C_{1}{\triangleright}C_{2}{::}C_{3}{\triangleright}C_{4},D_{1}{\triangleright}D_{2}{::}D_{3}{\triangleright}D_{4},$
$\displaystyle
D_{1}{\triangleright}D_{3}{::}D_{2}{\triangleright}D_{4},C_{1}\sqsubseteq
D_{1},C_{2}\sqsubseteq D_{2},C_{3}\sqsubseteq D_{3}\\}$

Then $\mathfrak{I}$ also satisfies the assertion $C_{4}\sqsubseteq D_{4}$.

######  Example 5.

Suppose the concept inclusions (1)–(3) are satisfied, as well as the following
analogy assertions555Note that $\textit{Cute }{\triangleright}\textit{
Cute}{::}\textit{Dangerous }{\triangleright}\textit{ Dangerous}$ is trivially
satisfied, since
$\sigma_{\emptyset}\in\mu(\textit{Cute},\textit{Cute})\cap\mu(\textit{Dangerous},\textit{Dangerous})$.:

$\displaystyle\textit{Young}\,{\triangleright}\textit{Adult}$
$\displaystyle{::}\textit{Young}\,{\triangleright}\textit{Adult}$
$\displaystyle\textit{Cat}\,{\triangleright}\textit{WildCat}$
$\displaystyle{::}\textit{Dog}\,{\triangleright}\textit{Wolf}$
$\displaystyle\textit{Cute}\,{\triangleright}\textit{Dangerous}$
$\displaystyle{::}\textit{Cute}\,{\triangleright}\textit{Dangerous}$
$\displaystyle\textit{Cute}\,{\triangleright}\textit{Cute}$
$\displaystyle{::}\textit{Dangerous}\,{\triangleright}\textit{Dangerous}$

Assuming the intersections involved are all non-empty, using Proposition 8 we
can infer
$(\textit{Young}\sqcap\textit{Cat}){\triangleright}(\textit{Adult}\sqcap\textit{WildCat}){::}(\textit{Young}\sqcap\textit{Dog}){\triangleright}(\textit{Adult}\sqcap\textit{Wolf})$.
Finally, using Proposition 11 we can infer that (4) holds.

Note that both $D_{1}{\triangleright}D_{2}{::}D_{3}{\triangleright}D_{4}$ and
$D_{1}{\triangleright}D_{3}{::}D_{2}{\triangleright}D_{4}$ are required for
the above proposition to hold (see the appendix for a counterexample that
shows this). For analogical proportions, adding both conditions makes no
difference, as $D_{1}{:}D_{2}\,{::}\,D_{3}{:}D_{4}$ and
$D_{1}{:}D_{3}\,{::}\,D_{2}{:}D_{4}$ are equivalent.

###  4.4 Alternative Semantics

As shown in Section 4.3, the proposed semantics for analogy assertions
satisfies the main desiderata from Section 3.2. We may wonder, however,
whether all aspects of the semantics are necessary for this to hold. We return
in particular to Condition 5 from Definition 1, which is perhaps the most
restrictive condition. In particular, let us define the notion of _weak domain
constrained interpretation_ as a tuple
$(\mathcal{I},[\mathcal{F}_{1},...,\mathcal{F}_{k}],\mathcal{X},\pi,\sim,\mathcal{S})$
that satisfies all conditions from Definition 1, apart from Condition 5. One
immediate consequence of dropping Condition 5 is that Proposition 4 is no
longer valid. As a result, in addition to analogy assertions of the form
$A_{1}{\triangleright}A_{2}{::}B_{1}{\triangleright}B_{2}$, with the semantics
defined in (15), we can now also consider _strong analogy assertions_ ,
denoted as
$A_{1}{\blacktriangleright}A_{2}{::}B_{1}{\blacktriangleright}B_{2}$, which
are satisfied if (15) is satisfied and moreover:

$\mu(A_{1},A_{2})=\mu(B_{1},B_{2})$

Under this weak semantics, $C$-transitivity (i.e. Proposition 7) is no longer
satisfied, neither for the standard analogy assertions nor for strong analogy
assertions (see the appendix for counterexamples). Regarding $S$-transitivity,
the variant in (17) remains valid and is furthermore also valid for strong
analogy assertions. However, the variant in (16) is no longer valid for
standard analogy assertions, although it is satisfied for strong analogy
assertions. In contrast, Proposition 9 remains valid for standard analogy
assertions, but it is not satisfied for strong analogy assertions. Proposition
8 is neither satisfied for standard analogy assertions nor for strong analogy
assertions. Finally, in terms of inference patterns, Proposition 10 remains
valid, but Proposition 11 does not, neither for standard nor strong analogy
assertions.

##  5 Conclusions

We have proposed a framework for analogy assertions of the form “$A$ is to $B$
what $C$ is to $D$” that is suitable for analogical reasoning in description
logics. The underlying assumption is that analogy assertions between concept
names can be learned from text, and that we can then lift these to obtain
analogy assertions between complex DL concepts. We have shown how the
resulting semantics allows us to infer concept inclusions using two analogy
based inference patterns. This complements other types of plausible inference
patterns, such as interpolation and similarity based reasoning.

There are two important lines for immediate future work. First, we plan to
study the computational complexity of reasoning in ${\cal
EL}_{\bot}^{\textit{ana}}$. Results from Ibáñez-García et al. (2020) provide a
coNP lower bound for concept subsumption w.r.t. ${\cal
EL}_{\bot}^{\textit{ana}}$ TBoxes. For the upper bound, one key issue would be
to relate the number of domains and features of concepts occurring in analogy
assertions, as well of those of existential restrictions over intra-domain
roles of such concepts. One would also need to establish a bound on the number
of features and domains. From the practical side we need mechanisms to deal
with the noisy nature of the available knowledge about betweenness and analogy
assertions (which typically would be learned from data) and the
inconsistencies that may introduce. To this end, we plan to study
probabilistic or non-monotonic extensions of our framework.

##  Appendix A Proofs

### Proof of Proposition 1

First note that $A_{2}\sqsubseteq B_{2}$ is equivalent to
$\varphi(B_{2})\subseteq\varphi(A_{2})$, since $A_{2}$ and $B_{2}$ are natural
concepts. Let $f\in\varphi(B_{2})$. We thus need to show that
$f\in\varphi(A_{2})$. If $f\notin\varphi(B_{1})$ then we must have
$f\in\varphi(A_{2})\setminus\varphi(A_{1})$, since
$A_{1}{:}A_{2}\,{::}\,B_{1}{:}B_{2}$ is satisfied. If $f\in\varphi(B_{1})$,
then we must have $f\in\varphi(A_{1})$ since $A_{1}\sqsubseteq B_{1}$ is
satisfied. Since $f\notin\varphi(B_{1})\setminus\varphi(B_{2})$ we must have
$f\notin\varphi(A_{1})\setminus\varphi(A_{2})$, which means
$f\in\varphi(A_{2})$.

### Proof of Proposition 2

Let us write $U=\\{(s_{1},t_{1}),...,(s_{k},t_{k})\\}$. We show for each
$g\in\mathcal{F}$ that $\sigma_{U^{\smallsmile}}(\sigma_{U}(g))=g$. If
$g\in\mathcal{F}_{s_{i}}$, for some $i\in\\{1,...,k\\}$, then by the
definition of domain translation, we have
$\sigma_{U^{\smallsmile}}(\sigma_{U}(g))=\sigma_{(t_{i},s_{i})}(\sigma_{(s_{i},t_{i})}(g))=g$.
If $g\notin\mathcal{F}_{s_{1}}\cup...\cup\mathcal{F}_{s_{k}}$, then
$\sigma_{U}(g)=g$. In that case, we also have
$g\notin\mathcal{F}_{t_{1}}\cup...\cup\mathcal{F}_{t_{k}}$, since
$g\in\mathcal{F}_{j}$ for some $j\in\delta(A_{1})\setminus\textit{src}(U)$ and
we know from (14) that
$\textit{tgt}(U)\cap(\delta(A_{1})\setminus\textit{src}(U))=\emptyset$. From
$g\notin\mathcal{F}_{t_{1}}\cup...\cup\mathcal{F}_{t_{k}}$ we find
$\sigma_{X^{\smallsmile}}(g)=g$ and in particular
$\sigma_{U^{\smallsmile}}(\sigma_{U}(g))=\sigma_{U^{\smallsmile}}(g)=g$.

### Proof of Proposition 3

We show this proposition in two steps.

######  Lemma 1.

We have

$\mu(A,C)\supseteq\\{\sigma_{U\oplus
V}\,|\,\sigma_{U}\in\mu(A,B),\sigma_{V}\in\mu(B,C)\\}$

Proof. Let $\sigma_{U}\in\mu(A,B)$ and $\sigma_{V}\in\mu(B,C)$. We need to
show that $\sigma_{U\oplus V}$ satisfies conditions, (12), (13) and (14)
w.r.t. the concept pair $(A,C)$.

First consider (13). Let $i\in\textit{src}(U\oplus V)$. If
$i\in\textit{src}(U)$ then we have $i\in\delta(A)$ since
$\sigma_{U}\in\mu(A,B)$. The only other possibility is that
$i\in\textit{src}(V)$ and $i\notin\textit{tgt}(U)$. Since
$\sigma_{V}\in\mu(B,C)$, we have that $i\in\textit{src}(V)$ implies
$i\in\delta(B)$. Since $\sigma_{U}\in\mu(A,B)$ and $i\notin\textit{tgt}(U)$,
this furthermore implies $i\in\delta(A)$. In all cases we thus have that (13)
is satisfied.

Next we show that (14) is satisfied, i.e. that $\textit{tgt}(U\oplus
V)\cap(\delta(A)\setminus\textit{src}(U\oplus V))=\emptyset$. Suppose
$k\in\textit{tgt}(U\oplus V)$; we show that
$k\notin\delta(A)\setminus\textit{src}(U\oplus V)$. We consider two cases:

  * •

Suppose $k\notin\delta(A)\setminus\textit{src}(U)$. Suppose
$k\in\delta(A)\setminus\textit{src}(U\oplus V)$ were to hold. This is only
possible if $k\in\textit{src}(U)\setminus\textit{src}(U\oplus V)$. By
definition of $\oplus$, this is only possible if $(k,j)\in U$ and $(j,k)\in V$
for some $j$. From $k\in\textit{tgt}(U\oplus V)$ we then find that $(i,k)\in
U$ for some $i$ and $k\notin\textit{src}(V)$. However, this implies that
$k\in\textit{tgt}(V)\cap(\delta(B)\setminus\textit{src}(V))$, which is a
contradiction since $\sigma_{V}\in\mu(B,C)$. We thus have
$k\notin\delta(A)\setminus\textit{src}(U\oplus V)$.

  * •

Suppose $k\in\delta(A)\setminus\textit{src}(U)$. Then $k\in\delta(B)$.
However, since $\sigma_{Y}\in\mu(B,C)$, we know that
$k\notin\delta(B)\setminus\textit{src}(V)$, hence we find
$k\in\textit{src}(V)$. In other words, $V$ contains some pair of the form
$(k,l)$. Furthermore, from
$\textit{tgt}(U)\cap(\delta(A)\setminus\textit{src}(U))=\emptyset$, we know
that $k\notin\textit{tgt}(U)$. By construction of $U\oplus V$ we find
$(k,l)\in U\oplus V$ and thus $k\in\textit{src}(U\oplus V)$, and in particular
$k\notin\delta(A)\setminus\textit{src}(U\oplus V)$.

Finally, we show that (12) is satisfied, i.e. that
$\varphi(C)=\\{\sigma_{U\oplus V}(f)\,|\,f\in\varphi(A)\\}$. Let
$f\in\varphi(A)$.

  * •

Suppose $(i,j)\in U$, $(j,k)\in V$ and $i\neq k$. Since
$\sigma_{U}\in\mu(A,B)$ and $\sigma_{V}\in\mu(B,C)$, we know that
$\sigma_{(i,j)}(f)\in\varphi(B)$ and
$\sigma_{(j,k)}(\sigma_{(i,j)}(f))\in\varphi(C)$. Since
$\sigma_{(j,k)}\circ\sigma_{(i,j)}=\sigma_{(i,k)}$ we find
$\sigma_{(i,k)}(f)\in\varphi(C)$, and in particular $\sigma_{U\oplus
V}(f)\in\varphi(C)$.

  * •

Suppose $(i,j)\in X$ and $j\notin\textit{src}(V)$. We then have
$\sigma_{(i,j)}(f)\in\varphi(B)$ as well as $\sigma_{(i,j)}(f)\in\varphi(C)$,
and in particular $\sigma_{U\oplus V}(f)\in\varphi(C)$.

  * •

Suppose $(j,k)\in Y$ and $j\notin\textit{tgt}(U)$. This implies that
$j\notin\textit{src}(U)$. We thus have $f\in\varphi(B)$,
$\sigma_{(j,k)}(f)\in\varphi(C)$ and in particular $\sigma_{U\oplus
V}(f)\in\varphi(C)$.

This already shows that $\varphi(C)\supseteq\\{\sigma_{U\oplus
V}(f)\,|\,f\in\varphi(A)\\}$. Conversely, suppose $f\in\varphi(C)$. Then we
know there must be some $g\in\varphi(B)$ such that $\sigma_{V}(g)=f$ and some
$h\in\varphi(A)$ such that $\sigma_{U}(h)=g$. Suppose $h\in\mathcal{F}_{i}$,
$g\in\mathcal{F}_{j}$ and $f\in\mathcal{F}_{k}$.

  * •

If $h\neq g$ and $g\neq f$, it must be the case that $(i,j)\in U$ and
$(j,k)\in V$. If $i\neq k$ we have $(i,k)\in U\oplus V$ and thus
$\sigma_{U\oplus V}(h)=f$. If $i=k$, we have $i\notin\textit{src}(U\oplus V)$
and thus again $\sigma_{U\oplus V}(h)=f$.

  * •

If $h\neq g$ and $g=f$, we have $j=k$, $j\notin\textit{src}(V)$ and thus
$(i,j)\in U\oplus V$, meaning $\sigma_{U\oplus V}(h)=\sigma_{U}(h)=g=f$.

  * •

If $h=g$ and $g\neq f$, we have $i=j$, $j\notin\textit{tgt}(U)$ and thus
$(j,k)\in U\oplus V$, meaning $\sigma_{U\oplus V}(h)=\sigma_{U\oplus
V}(g)=\sigma_{V}(g)=f$.

This shows $\varphi(C)\subseteq\\{\sigma_{U\oplus V}(f)\,|\,f\in\varphi(A)\\}$
❏

To complete the proof of Proposition 3, we now also show the following result

######  Lemma 2.

If $\mu(A,B)\neq\emptyset$ and $\mu(B,C)\neq\emptyset$ then it holds that:

$\mu(A,C)\subseteq\\{\sigma_{U\oplus
V}\,|\,\sigma_{U}\in\mu(A,B),\sigma_{V}\in\mu(B,C)\\}$

Proof. Let $\sigma_{Z}\in\mu(A,C)$. We show that there are mappings
$\sigma_{U^{*}}\in\mu(A,B)$ and $\sigma_{V^{*}}\in\mu(B,C)$ such that
$Z=U^{*}\oplus V^{*}$.

Let $\sigma_{U}$ and $\sigma_{V}$ be arbitrary elements from $\mu(A,B)$ and
$\mu(B,C)$ respectively. If $Z=U\oplus V$ then we can simply choose $U^{*}=U$
and $V^{*}=V$. Now suppose there is some feature $f\in\mathcal{F}_{i}$ such
that $\sigma_{U\oplus V}(f)\neq\sigma_{Z}(f)$. Let us write $g=\sigma_{U\oplus
V}(f)$ and $g^{\prime}=\sigma_{Z}(f)$. Furthermore, let $f^{\prime}$ and
$f^{\prime\prime}$ be the features from $\varphi(A)$ such that
$\sigma_{U\oplus V}(f^{\prime})=g^{\prime}$ and
$\sigma_{Z}(f^{\prime\prime})=f$. Let us write $i,i^{\prime},i^{\prime\prime}$
for the domains of $f,f^{\prime},f^{\prime\prime}$ and $j,j^{\prime}$ for the
domains of $g,g^{\prime}$ respectively. Note that we then have

$\displaystyle\varphi(A)\cap\mathcal{F}_{i}$ $\displaystyle=\\{\sigma_{U\oplus
V}^{-1}(x)\,|\,x\in\varphi(C)\cap\mathcal{F}_{j}\\}$
$\displaystyle=\\{\sigma_{Z}^{-1}(x)\,|\,x\in\varphi(C)\cap\mathcal{F}_{j^{\prime}}\\}$

from which we find

$\displaystyle\varphi(C)\cap\mathcal{F}_{j^{\prime}}$
$\displaystyle=\\{\sigma_{Z}(\sigma_{U\oplus
V}^{-1}(x))\,|\,x\in\varphi(C)\cap\mathcal{F}_{j}\\}$
$\displaystyle\varphi(C)\cap\mathcal{F}_{j}$ $\displaystyle=\\{\sigma_{U\oplus
V}(\sigma_{Z}^{-1}(x))\,|\,x\in\varphi(C)\cap\mathcal{F}_{j^{\prime}}\\}$

and in particular thus also:

$\displaystyle\varphi(C)\cap\mathcal{F}_{j^{\prime}}$
$\displaystyle=\\{\sigma_{(j,j^{\prime})}(x)\,|\,x\in\varphi(C)\cap\mathcal{F}_{j}\\}$
(20) $\displaystyle\varphi(C)\cap\mathcal{F}_{j}$
$\displaystyle=\\{\sigma_{(j^{\prime},j)}(x)\,|\,x\in\varphi(C)\cap\mathcal{F}_{j^{\prime}}\\}$
(21)

We show that we can always find $U^{\prime}$ and $V^{\prime}$ such that
$\sigma_{U^{\prime}}\in\mu(A,B)$, $\sigma_{V^{\prime}}\in\mu(B,C)$,
$\sigma_{U^{\prime}\oplus V^{\prime}}(f)=\sigma_{Z}(f)$, and such that for
each feature $f^{\prime}$ for which we had $\sigma_{U\oplus
V}(f^{\prime})=\sigma_{Z}(f^{\prime})$, we have $\sigma_{U^{\prime}\oplus
V^{\prime}}(f^{\prime})=\sigma_{Z}(f^{\prime})$. Thus, given that the set of
features $\mathcal{F}$ is finite, by repeating the same process, we will end
up with mappings $\sigma_{U^{*}}$ and $\sigma_{V^{*}}$ such that
$\sigma_{U^{*}\oplus V^{*}}=\sigma_{Z}$.

  * •

Suppose $U$ contains a pair of the form $(i,l)$ and $V$ contains pair of the
form $(l,j)$.

    * –

Suppose $V$ also contains a pair of the form $(l^{\prime},j^{\prime})$. Let
$U^{\prime}=U$ and
$V^{\prime}=(V\setminus\\{(l,j),(l^{\prime},j^{\prime})\\})\cup\\{(l,j^{\prime}),(l^{\prime},j)\\}$.
From (20)–(21), together with the transitivity properties of the mappings
$\sigma_{(i,j)}$ (i.e. Condition 3 from Definition 1), it follows that

$\displaystyle\varphi(C)\cap\mathcal{F}_{j^{\prime}}$
$\displaystyle=\\{\sigma_{(l,j^{\prime})}(x)\,|\,x\in\varphi(B)\cap\mathcal{F}_{l}\\}$
$\displaystyle\varphi(C)\cap\mathcal{F}_{j}$
$\displaystyle=\\{\sigma_{(l,j)}(x)\,|\,x\in\varphi(B)\cap\mathcal{F}_{l^{\prime}}\\}$

It follows that $\sigma_{V^{\prime}}\in\mu(B,C)$ while $U^{\prime}$ and
$V^{\prime}$ satisfy the required conditions.

    * –

Suppose $V$ does not contain any pair of the form $(l^{\prime},j^{\prime})$
but $U$ contains a pair of the form $(l^{\prime},j^{\prime})$, then we define
$U^{\prime}=(U\setminus\\{(l^{\prime},j^{\prime})\\})\cup\\{(l^{\prime},j)\\}$
and $V^{\prime}=(V\setminus\\{(l,j)\\})\cup\\{(l,j^{\prime})\\}$. Similarly as
in the previous case, we find that $U^{\prime}$ and $V^{\prime}$ satisfy the
requirements.

    * –

If $U$ does not contain any pair of the form $(l^{\prime},j^{\prime})$ either,
then it must be the case that $\sigma_{U\oplus V}(f^{\prime})=f^{\prime}$ and
$i^{\prime}=j^{\prime}$. In this case, we can choose $U^{\prime}=U$ and
$V^{\prime}=(V\setminus\\{(l,j)\\})\cup\\{(l,j^{\prime}),(i^{\prime},j)\\}$.

  * •

Suppose $U$ contains a pair of the form $(i,j)$.

    * –

If $V$ contains a pair of the form $(l^{\prime},j^{\prime})$, then we can
choose $U^{\prime}=(U\setminus\\{(i,j)\\})\cup\\{(i,j^{\prime})\\}$ and
$V^{\prime}=(V\setminus\\{(l^{\prime},j^{\prime})\\})\cup\\{(l^{\prime},j)\\}$.

    * –

If $V$ does not contain a pair of the form $(l^{\prime},j^{\prime})$, but $U$
contains such a pair then we can choose
$U^{\prime}=(U\setminus\\{(i,j),(l^{\prime},j^{\prime})\\})\cup\\{(i,j^{\prime}),(l^{\prime},j)\\}$
and $V^{\prime}=V$.

    * –

If $U$ does not contain a pair of the form $(l^{\prime},j^{\prime})$ either,
then $i^{\prime}=j^{\prime}$ and we can choose
$U^{\prime}=(U\setminus\\{(i,j)\\})\cup\\{(i,j^{\prime})\\}$ and
$V^{\prime}=V\cup\\{(i^{\prime},j)\\}$.

  * •

Suppose $V$ contains a pair of the form $(i,j)$.

    * –

Suppose $V$ also contains a pair of the form $(l^{\prime},j^{\prime})$. Then
we can choose $U^{\prime}=U$ and
$V^{\prime}=(V\setminus\\{(i,j),(l^{\prime},j^{\prime})\\})\cup\\{(i,j^{\prime}),(l^{\prime},j)\\}$.

    * –

Suppose $V$ does not contain a pair of the form $(l^{\prime},j^{\prime})$ but
$U$ contains such a pair. Then we can choose
$U^{\prime}=(U\setminus\\{(l^{\prime},j^{\prime})\\})\cup\\{(l^{\prime},j)\\}$
and $V^{\prime}=(V\setminus\\{(i,j)\\})\cup\\{(i,j^{\prime})\\}$.

    * –

Suppose $U$ does not contain a pair of the form $(l^{\prime},j^{\prime})$
either. Then $i^{\prime}=l^{\prime}$ and we can choose $U^{\prime}=U$ and
$V^{\prime}=(V\setminus\\{(i,j)\\})\cup\\{(i,j^{\prime}),(i^{\prime},j)\\}$.

We thus find that suitable sets $U^{\prime}$ and $V^{\prime}$ can be found in
all cases.  ❏

### Proof of Proposition 4

We first show the following lemmas.

######  Lemma 3.

Let
$\mathfrak{I}=(\mathcal{I},[\mathcal{F}_{1},...\mathcal{F}_{k}],\mathcal{X},\pi,\sim,\mathcal{S})$
be a domain-constrained interpretation. If $i,j\in\delta(A)$ such that
$(i,j)\in\sim$ and $i\neq j$, it holds that $A^{\mathcal{I}}=\emptyset$.

Proof. This follows immediately from Conditions 1 and 5 of Definition 1.  ❏

######  Lemma 4.

Let
$\mathfrak{I}=(\mathcal{I},[\mathcal{F}_{1},...\mathcal{F}_{k}],\mathcal{X},\pi,\sim,\mathcal{S})$
be a domain-constrained interpretation. If $\mu(A,B)\neq\emptyset$ then there
is some $\sigma_{u}\in\mu(A,B)$ such that for every $\sigma_{V}\in\mu(A,B)$ it
holds that $U\subseteq V$.

Proof. Suppose that $\sigma_{U},\sigma_{V}\in\mu(A,B)$ such that $U$ and $V$
are minimal, i.e. for any $U^{\prime}\subset U$ or $V^{\prime}\subset V$ we
have $\sigma_{U^{\prime}}\notin\mu(A,B)$ and
$\sigma_{V^{\prime}}\notin\mu(A,B)$. Now suppose $U\neq V$, i.e. suppose that
there is some pair $(i_{1},i_{2})\in U\setminus V$ and some pair
$(j_{1},j_{2})\in V\setminus U$.

First assume $i_{1}=j_{1}$. Since $U$ and $V$ were assumed to be minimal, we
have $i_{1},j_{1}\in\delta(A)$ and thus we must also have
$i_{2},j_{2}\in\delta(B)$. However, that means $\varphi(B)$ contains some
$f\in\mathcal{F}_{i_{2}}$ and some $g\in\mathcal{F}_{j_{2}}$, while
$(i_{2},j_{2})\in\sim$. We thus find from Lemma 3 that
$B^{\mathcal{I}}=\emptyset$, or in other words that $\varphi(B)=\mathcal{F}$.
This also entails that $\varphi(A)=\mathcal{F}$. The only way to choose
$\sigma_{U}$ and $\sigma_{V}$ such that $U$ and $V$ are minimal is thus to
choose $U=V=\emptyset$.

Now assume there is no pair $(j_{1},j_{2})\in V\setminus U$ such that
$i_{1}=j_{1}$. Since $U$ was assumed to be minimal, we must have some
$f\in\mathcal{F}_{i_{1}}\cap\varphi(A)$. Since, by assumption, we have no pair
of the form $(i_{1},j)$ in $V$, we must also have $f\in\varphi(B)$. We thus
find that $f$ and $\sigma_{U}(f)$ both belong to $\varphi(B)$, but
$f\in\mathcal{F}_{i_{1}}$ and $\sigma_{U}(f)\in\mathcal{F}_{i_{2}}$. Since $U$
was assumed to be minimal, we also have $i_{1}\neq i_{2}$, hence it again
follows that $B^{\mathcal{I}}=\emptyset$, and thus
$\varphi(A)=\varphi(B)=\mathcal{F}$ and $U=V=\emptyset$.  ❏

From Lemma 4, we know that $\mu(A,B)$ contains some element $\sigma_{U}$ such
that $U\subseteq V$ for each $\sigma_{V}\in\mu(A,B)$. Now suppose $U\neq V$
and let $(i,j)\in V\setminus U$. Note that by (13) we have that
$i\in\delta(A)$. We can thus only have
$\sigma_{U}(\varphi(A))=\sigma_{V}(\varphi(A))$ if $U$ contains a pair of the
form $(i,k)$. That means that $i,k\in\delta(B)$ with $i\neq k$, and thus
$A^{\mathcal{I}}=B^{\mathcal{I}}=\emptyset$ (using Lemma 3).

### Proof of Proposition 5

We first show the following lemma.

######  Lemma 5.

Suppose that $\sigma_{X}\in\mu(A_{1},A_{2})$. Then
$\sigma_{X^{\smallsmile}}\in\mu(A_{2},A_{1})$.

Proof. We first show that

$\textit{tgt}(X^{\smallsmile})\cap(\delta(A_{2})\setminus\textit{src}(X^{\smallsmile}))=\emptyset$

which is equivalent to:

$\textit{src}(X)\cap(\delta(A_{2})\setminus\textit{tgt}(X))=\emptyset$

Let $i\in\delta(A_{2})\setminus\textit{tgt}(X)$. Then there must be some
$f\in\varphi(A_{2})$ such that $f\in\mathcal{F}_{i}$. But since
$i\notin\textit{tgt}(X)$ this is only possible if $f\in\varphi(A_{1})$ and
$i\notin\textit{src}(X)$. We thus have
$\textit{src}(X)\cap(\delta(A_{2})\setminus\textit{tgt}(X))=\emptyset$. We now
show that
$\varphi(A_{1})=\\{\sigma_{X^{\smallsmile}}(f)\,|\,f\in\varphi(A_{2})\\}$.
Since $\sigma_{X}\in\mu(A_{1},A_{2})$, this means that we need to show:

$\varphi(A_{1})=\\{\sigma_{X^{\smallsmile}}(\sigma_{X}(g))\,|\,g\in\varphi(A_{1})\\}$

which follows immediately from Proposition 2. Finally, it is also clear that
(13) is satisfied for $\sigma_{X^{\smallsmile}}$ if this condition is
satisfied for $\sigma_{X}$ ❏

Since $(U^{\smallsmile})^{\smallsmile}=U$, we have the following corollary.

######  Corollary 1.

It holds that:

$\displaystyle\mu(A_{2},A_{1})=\\{\sigma_{U^{\smallsmile}}\,|\,\sigma_{U}\in\mu(A_{1},A_{2})\\}$

The main result directly follows from this corollary.

### Proof of Proposition 6

We show both transitivity properties separately.

######  Lemma 6.

It holds that:

$\\{A_{1}{\triangleright}A_{2}{::}B_{1}{\triangleright}B_{2},B_{1}{\triangleright}B_{2}{::}C_{1}{\triangleright}C_{2}\\}\models
A_{1}{\triangleright}A_{2}{::}C_{1}{\triangleright}C_{2}$

Proof. Assume that $A_{1}{\triangleright}A_{2}{::}B_{1}{\triangleright}B_{2}$
and $B_{1}{\triangleright}B_{2}{::}C_{1}{\triangleright}C_{2}$ are satisfied
in some domain-constrained interpretation $\mathfrak{I}$. We then have that
there is some $\sigma_{U}\in\mu(A_{1},A_{2})\cap\mu(B_{1},B_{2})$ and some
$\sigma_{V}\in\mu(B_{1},B_{2})\cap\mu(C_{1},C_{2})$. By Proposition 4, we have
$\sigma_{U}=\sigma_{V}$ and thus we find that
$\mu(A_{1},A_{2})\cap\mu(C_{1},C_{2})\neq\emptyset$.  ❏

######  Lemma 7.

It holds that:

$\\{A_{1}{\triangleright}A_{2}{::}B_{1}{\triangleright}B_{2},A_{2}{\triangleright}A_{3}{::}B_{2}{\triangleright}B_{3}\\}\models
A_{1}{\triangleright}A_{3}{::}B_{1}{\triangleright}B_{3}$

Proof. Assume that $A_{1}{\triangleright}A_{2}{::}B_{1}{\triangleright}B_{2}$
and $A_{2}{\triangleright}A_{3}{::}B_{2}{\triangleright}B_{3}$ are satisfied
in some domain-constrained interpretation $\mathfrak{I}$. Then there exists
some $\sigma_{U}\in\mu(A_{1},A_{2})\cap\mu(B_{1},B_{2})$ and some
$\sigma_{V}\in\mu(A_{2},A_{3})\cap\mu(B_{2},B_{3})$. By Proposition 3 we then
have that $\sigma_{U\oplus V}\in\mu(A_{1},A_{3})\cap\mu(B_{1},B_{3})$, and
hence that $A_{1}{\triangleright}A_{3}{::}B_{1}{\triangleright}B_{3}$ is
satisfied.  ❏

### Proof of Proposition 7

Assume that $A_{1}{\triangleright}B_{1}{::}B_{2}{\triangleright}A_{2}$ and
$A_{1}{\triangleright}C_{1}{::}C_{2}{\triangleright}A_{2}$ are satisfied in
some domain-constrained interpretation $\mathfrak{I}$. There exist some
$\sigma_{U}\in\mu(A_{1},B_{1})\cap\mu(B_{2},A_{2})$ and some
$\sigma_{V}\in\mu(A_{1},C_{1})\cap\mu(C_{2},A_{2})$.

First assume that $A_{1}^{\mathcal{I}}=\emptyset$. Then clearly we also have
$B_{1}^{\mathcal{I}}=C_{1}^{\mathcal{I}}=\emptyset$, since
$\varphi(A_{1})=\mathcal{F}$ and
$|\varphi(A_{1})|=|\varphi(B_{1})|=|\varphi(C_{1})|$. If moreover
$A_{2}^{\mathcal{I}}=\emptyset$, then we similarly also find
$B_{2}^{\mathcal{I}}=C_{2}^{\mathcal{I}}=\emptyset$ and the result is
trivially satisfied. If $A_{2}^{\mathcal{I}}\neq\emptyset$, then the only
possibility is that $U=V=\emptyset$. Indeed, if e.g. $(i,k)\in V$ then $V$
would need to contain some element of the form $(j,i)$ with $(i,j)\in\sim$,
which would entail $C_{2}^{\mathcal{I}}=\emptyset$ since
$\textit{src}(V)\subseteq\delta(C_{2})$ and $i,j\in\delta(C_{2})$ implies
$C_{2}^{\mathcal{I}}=0$ by Lemma 3. Thus we have
$A_{2}^{\mathcal{I}}=B_{2}^{\mathcal{I}}=C_{2}^{\mathcal{I}}$, meaning that
the result is satisfied. The case where $A_{2}^{\mathcal{I}}=\emptyset$ and
$A_{1}^{\mathcal{I}}\neq\emptyset$ is analogous.

We now show that the result holds for the case where
$A_{1}^{\mathcal{I}}\neq\emptyset$ and $A_{2}^{\mathcal{I}}\neq\emptyset$.
From Corollary 1 and Proposition 3 we know that then
$\mu_{U^{\smallsmile}\oplus V}\in\mu(B_{1},C_{1})$ and $\mu_{V\oplus
U^{\smallsmile}}\in\mu(C_{2},B_{2})$. To complete the proof, we show that
$\mu_{U^{\smallsmile}\oplus V}=\mu_{V\oplus
U^{\smallsmile}}=\mu_{U^{\smallsmile}\cup V}$, from which it follows in
particular that $\mu_{U^{\smallsmile}\oplus
V}\in\mu(B_{1},C_{1})\cap\mu(C_{2},B_{2})$, meaning that
$A_{1}{\triangleright}A_{3}{::}B_{1}{\triangleright}B_{3}$ is satisfied.

Suppose that there are elements $i,j,k$ such that $(i,j)\in U^{\smallsmile}$
and $(j,k)\in V$. Then we have $i\in\delta(A_{2})$ since
$\textit{src}(U^{\smallsmile})\subseteq\delta(A_{2})$. However, we also have
$k\in\delta(A_{2})$ since $\textit{src}(V)\subseteq\delta(C_{2})$ and
$\varphi(A_{2})=\sigma_{V}(\varphi(C_{2}))$. Since $(i,k)\in\sim$ and we
assumed $A_{2}^{\mathcal{I}}\neq\emptyset$, it follows that $i=k$. Since this
is the case for all $i,j,k$ such that $(i,j)\in U^{\smallsmile}$ and $(j,k)\in
V$, it follows from the definition of $\oplus$ that $U^{\smallsmile}\oplus
V=U^{\smallsmile}\cup V$. In the same way we find that $V\oplus
U^{\smallsmile}=U^{\smallsmile}\cup V$.

### Proof of Proposition 8

We first show the following lemma.

######  Lemma 8.

Let
$\mathfrak{I}=(\mathcal{I},[\mathcal{F}_{1},...,\mathcal{F}_{k}],\mathcal{X},\pi,\sim,\mathcal{S})$
be a domain-constrained interpretation satisfying
$(A_{1}{\sqcap}B_{1})^{\mathcal{I}}\neq\emptyset$ and
$(A_{2}{\sqcap}B_{2})^{\mathcal{I}}\neq\emptyset$. Let
$\sigma_{U}\in\mu(A_{1},B_{1})$ and $\sigma_{V}\in\mu(A_{2},B_{2})$. It holds
that $\sigma_{U\cup V}\in\mu(A_{1}\sqcap B_{1},A_{2}\sqcap B_{2})$.

Proof. We first show that $\sigma_{U\cup V}$ is a valid domain translation:

  * •

All pairs in $U\cup V$ should have a different source domain, i.e. we must
have that for all $(i,j)\in U$ and $(i,k)\in V$ it holds that $j=k$. To see
why this is satisfied, note that $(i,j)\in U$ and $(i,k)\in V$ imply that
$j\in\delta(A_{2})$ and $k\in\delta(B_{2})$. From Lemma 3, we know that $j\neq
k$ would imply $(A_{2}\sqcap B_{2})^{\mathcal{I}}=\emptyset$.

  * •

All pairs in $U\cup V$ should have a different target domain, i.e. for all
$(i,k)\in U$ and $(j,k)\in V$ we must have that $i=j$. To see why this is
satisfied, note that $(i,k)\in U$ and $(j,k)\in V$ mean $i\in\delta(A_{1})$
and $j\in\delta(B_{1})$. We thus find that $i\neq j$ would imply $(A_{1}\sqcap
B_{1})^{\mathcal{I}}=\emptyset$.

Next we show that $\textit{tgt}(U\cup V)\cap(\delta(A_{1}\sqcap
B_{1})\setminus\textit{src}(U\cup V))=\emptyset$. Suppose that there were some
$i\in\textit{tgt}(U\cup V)\cap(\delta(A_{1}\sqcap
B_{1})\setminus\textit{src}(U\cup V))$. In other words, suppose we had
$i\in\textit{tgt}(U)\cup\textit{tgt}(V)$,
$i\in\delta(A_{1})\cup\delta(B_{1})$, $i\notin\textit{src}(U)$ and
$i\notin\textit{src}(V)$. Suppose in particular that $i\in\textit{tgt}(U)$;
the case where $i\in\textit{tgt}(V)$ is entirely analogous. Since
$\sigma_{U}\in\mu(A_{1},A_{2})$ and $i\notin\textit{src}(U)$ we know that
$i\notin\delta(A_{1})$, and thus in particular that $i\in\delta(B_{1})$. From
$i\in\textit{tgt}(U)$, we know that there must be some $(j,i)\in U$ such that
$j\in\delta(A_{1})$ and $(j,i)\in\sim$. Together with $i\in\delta(B_{1})$ we
find $i,j\in\delta(A_{1}\sqcap B_{1})$, which would imply $(A_{1}\sqcap
B_{1})^{\mathcal{I}}=\emptyset$, using Lemma 3.

Next we show that for $f\in\varphi(A_{1})$ it must be the case that
$\sigma_{U\cup V}(f)=\sigma_{U}(f)$. Assume $f\in\mathcal{F}_{i}$. If
$i\in\textit{src}(U)$ then there is some element $(i,j)\in U$ and
$\sigma_{U\cup V}(f)=\sigma_{U}(f)=\sigma_{(i,j)}(f)$. If
$i\notin\textit{src}(U\cup V)$ then we trivially have $\sigma_{U\cup
V}(f)=\sigma_{U}(f)=f$. Finally, assume that
$i\in\textit{src}(V)\setminus\textit{src}(U)$, then $V$ contains some element
$(i,j)$ from $\sim$ such that $i\in\delta(A_{2})$ and $j\in\delta(B_{2})$, but
this would imply $(A_{2}\sqcap B_{2})^{\mathcal{I}}=\emptyset$ using Lemma 3.
Similarly, we also find that for $f\in\varphi(B_{1})$ it must be the case that
$\sigma_{U\cup V}(f)=\sigma_{V}(f)$. It follows that $\varphi(A_{2}\sqcap
B_{2})=\\{\sigma_{U\cup V}(f)\,|\,f\in\varphi(A_{1}\sqcap B_{1})\\}$. Indeed:

$\displaystyle\\{\sigma_{U\cup V}(f)\,|\,f\in\varphi(A_{1}\sqcap B_{1})\\}$
$\displaystyle=\\{\sigma_{U\cup
V}(f)\,|\,f\in\varphi(A_{1})\\}\cup\\{\sigma_{U\cup
V}(f)\,|\,f\in\varphi(B_{1})\\}$
$\displaystyle=\\{\sigma_{U}(f)\,|\,f\in\varphi(A_{1})\\}\cup\\{\sigma_{V}(f)\,|\,f\in\varphi(B_{1})\\}$
$\displaystyle=\varphi(A_{2})\cup\varphi(B_{2})$
$\displaystyle=\varphi(A_{1}\sqcap B_{2})$

❏

Now we return to the main result. From
$A_{1}{\triangleright}A_{2}{::}A_{3}{\triangleright}A_{4}$ and
$B_{1}{\triangleright}B_{2}{::}B_{3}{\triangleright}B_{4}$ we know that there
exists some $\sigma_{U}\in\mu(A_{1},A_{2})\cap\mu(A_{3},A_{4})$ and
$\sigma_{V}\in\mu(B_{1},B_{2})\cap\mu(B_{3},B_{4})$. From Lemma 8 we then find
$\sigma_{U\cup V}\in\mu(A_{1}\sqcap B_{1},A_{2}\sqcap
B_{2})\cap\mu(A_{3}\sqcap B_{2},A_{4}\sqcap B_{4})$, which means that
$(A_{1}\sqcap B_{1}){\triangleright}(A_{2}\sqcap B_{2}){::}(A_{3}\sqcap
B_{3}){\triangleright}(A_{4}\sqcap B_{4})$ is satisfied.

### Proof of Proposition 9

######  Lemma 9.

Let
$\mathfrak{I}=(\mathcal{I},[\mathcal{F}_{1},...,\mathcal{F}_{k}],\mathcal{X},\pi,\sim,\mathcal{S})$
be a domain constrained interpretation and let $r$ be an intra-domain role. It
holds that $\mu(A,B)\subseteq\mu(\exists r.A,\exists r.B)$.

Proof. Let $\sigma_{U}\in\mu(A,B)$. We first show that $\varphi(\exists
r.B)=\sigma_{U}(\varphi(\exists r.A))$. We find:

$\displaystyle\sigma_{U}(\varphi(\exists r.A))$
$\displaystyle=\sigma_{U}(\kappa_{r}(\varphi(A)))$
$\displaystyle=\kappa_{r}(\sigma_{U}(\varphi(A)))$
$\displaystyle=\kappa_{r}(\varphi(B))$ $\displaystyle=\varphi(\exists r.B)$

Finally, the fact that $\textit{src}(U)\subseteq\delta(\exists r.A)$ and
$\textit{tgt(U)}\cap(\delta(\exists r.A)\setminus\textit{src}(U))=\emptyset$
are satisfied, follows from the fact that $\sigma_{U}\in\mu(A,B)$ and the fact
that $\delta(\exists r.A)=\delta(A)$, where the latter follows immediately
from the definition of intra-domain relation.  ❏

We now show that (18) and (19) hold. Since
$A{\triangleright}B{::}C{\triangleright}D$ is satisfied, there must exist some
$\sigma_{U}\in\mu(A,B)\cap\mu(C,D)$. From Lemma 9, we find that
$\sigma_{U}\in\mu(\exists r.A,\exists r.B)\cap\mu(\exists r.C,\exists r.D)$,
and thus that (18) is satisfied. Similarly, we also find that
$\sigma_{U}\in\mu(A,B)\cap\mu(\exists r.C,\exists r.D)$, and thus that (19) is
satisfied.

### Proof of Proposition 10

Assume that $\mathfrak{I}$ satisfies
$A_{1}{\triangleright}B_{1}{::}A_{2}{\triangleright}B_{2}$ and
$A_{1}\sqsubseteq A_{2}$. We need to show that $\mathfrak{I}$ satisfies
$B_{1}\sqsubseteq B_{2}$, or equivalently, that
$\varphi(B_{2})\subseteq\varphi(B_{1})$. Let $f\in\varphi(B_{2})$. Since
$\mathfrak{I}$ satisfies
$A_{1}{\triangleright}B_{1}{::}A_{2}{\triangleright}B_{2}$ there exists some
$\sigma_{U}\in\mu(A_{1},B_{2})\cap\mu(A_{2},B_{2})$. Hence there must be some
$g\in\varphi(A_{2})$ such that $\sigma_{U}(g)=f$. Since $A_{1}\sqsubseteq
A_{2}$ is satisfied, we have $g\in\varphi(A_{1})$, which in turn implies that
$\sigma_{U}(g)\in\varphi(B_{1})$, i.e. $f\in\varphi(A_{1})$.

### Proof of Proposition 11

If $A_{4}^{\mathcal{I}}=\emptyset$ then the conclusion holds trivially.
Moreover, if $A_{3}^{\mathcal{I}}=\emptyset$ then we have
$\varphi(A_{3})=\mathcal{F}$, hence from
$A_{1}{\triangleright}A_{2}{::}A_{3}{\triangleright}A_{4}$ we find
$\varphi(A_{4})=\mathcal{F}$ and thus $A_{4}^{\mathcal{I}}=\emptyset$, hence
again the conclusion holds trivially. From $A_{1}^{\mathcal{I}}\neq\emptyset$
we similarly find $A_{2}^{\mathcal{I}}\neq\emptyset$. If
$B_{4}^{\mathcal{I}}=\emptyset$ then we also have
$B_{3}^{\mathcal{I}}=\emptyset$, which would imply
$A_{3}^{\mathcal{I}}=\emptyset$ and thus also $A_{4}^{\mathcal{I}}=\emptyset$,
meaning that the conclusion is again trivially satisfied. The same holds
whenever $B_{3}^{\mathcal{I}}=\emptyset$. Finally, since
$A_{1}^{\mathcal{I}}\neq\emptyset$, it must be the case that
$A_{2}^{\mathcal{I}}\neq\emptyset$, $B_{1}^{\mathcal{I}}\neq\emptyset$ and
$B_{2}^{\mathcal{I}}\neq\emptyset$. In the following, we can thus assume
w.l.o.g. that $A_{i}^{\mathcal{I}}\neq\emptyset$ and
$B_{i}^{\mathcal{I}}\neq\emptyset$ for $i\in\\{1,2,3,4\\}$

Suppose that $\mathfrak{I}$ satisfies the stated condition. Let
$\sigma_{U}\in\mu(A_{1},A_{2})\cap\mu(A_{3},A_{4})$,
$\sigma_{U^{\prime}}\in\mu(A_{1},A_{3})\cap\mu(A_{2},A_{4})$,
$\sigma_{V}\in\mu(B_{1},B_{2})\cap\mu(B_{3},B_{4})$ and
$\sigma_{V^{\prime}}\in\mu(B_{1},B_{3})\cap\mu(B_{2},B_{4})$. We need to show
that $\mathcal{I}$ satisfies $A_{4}\sqsubseteq B_{4}$, which is equivalent to
$\varphi(B_{4})\subseteq\varphi(A_{4})$. Let $f\in\varphi(B_{4})$, with
$f\in\mathcal{F}_{i}$. Then there must be some $g\in\varphi(A_{3})$ such that
$\sigma_{Y}(g)=f$.

  * •

If $f=g$, then it must be the case that either
$i\in\delta(B_{1})\cap\delta(B_{2})$ or that
$i\notin\delta(B_{1})\cup\delta(B_{2})$.

    * –

Suppose $i\in\delta(B_{1})\cap\delta(B_{2})$, then there some
$h\in\varphi(B_{1})\cap\varphi(B_{2})\cap\mathcal{F}_{i}$. Since
$A_{1}\sqsubseteq B_{1}$ and $A_{2}\sqsubseteq B_{2}$ are satisfied, that
means $h\in\varphi(A_{1})\cap\varphi(A_{2})$, and in particular
$i\in\delta(A_{1})\cap\delta(A_{2})$, which implies $i\notin\textit{src}(U)$.
From $f\in\varphi(B_{3})$, we find $f\in\varphi(A_{3})$, since
$A_{3}\sqsubseteq B_{3}$ is satisfied, which in turn entails
$f\in\varphi(A_{4})$ since $i\notin\textit{src}(U)$ and
$\sigma_{U}\in\mu(A_{3},A_{4})$.

    * –

Suppose $i\notin\delta(B_{1})\cup\delta(B_{2})$. If $i\notin\textit{src}(U)$,
we find $f\in\varphi(A_{4})$ as in the previous case. Now suppose
$i\in\textit{src}(U)$. Since $\sigma_{U^{\prime}}\in\mu(B_{1},B_{3})$ there
must be some $(j,i)\in U^{\prime}$ such that $j\in\delta(B_{1})$. Note that
$i\notin\delta(B_{1})$ hence $i\neq j$. Since $A_{1}\sqsubseteq B_{1}$ is
satisfied, we then also have $j\in\delta(A_{1})$. However, from
$i\in\textit{src}(U)$ it follows that $i\in\delta(A_{1})$. Using Lemma 3, from
$i,j\in\delta(A_{1})$ and $i\neq j$ we find $A_{1}^{\mathcal{I}}=\emptyset$,
which contradicts our assumption that $A_{1}$ was non-empty. Hence the case
where $i\in\textit{src}(U)$ cannot occur.

  * •

Now suppose $f\neq g$, and let $g\in\mathcal{F}_{j}$. Then we have $(j,i)\in
U$, with $i\neq j$, and thus $j\in\delta(B_{1})$ and $i\in\delta(B_{2})$.
Since $A_{1}\sqsubseteq B_{1}$, $A_{2}\sqsubseteq B_{2}$ and $A_{3}\sqsubseteq
B_{3}$ are satisfied, we also have $j\in\delta(A_{1})\cap\delta(A_{3})$ and
$i\in\delta(A_{2})$. From $i\neq j$ and Lemma 3, it follows that
$i\notin\delta(A_{1})$ and $j\notin\delta(A_{2})$. Moreover, by Lemma 3 and
the non-emptiness of $A_{1}$, there cannot be any $l\in\delta(A_{1})$ such
that $l\neq j$ and $(l,i)\in\sim$, as this would also imply $(l,j)\in\sim$. We
thus have that $(j,i)\in U$. Given that $g\in\varphi(B_{3})$ and the fact that
$A_{3}\sqsubseteq B_{3}$ is satisfied, we find $g\in\varphi(A_{3})$. Since
$(j,i)\in U$ and $\sigma_{U}\in\mu(A_{3},A_{4})$, it follows that
$f\in\varphi(A_{4})$.

##  Appendix B Counterexamples

### Counterexamples for Section 3.2

The following example shows that rule extrapolation is not valid for
analogical proportions.

######  Example 6.

Consider a feature-enriched interpretation $\mathfrak{I}$ s.t.:

$\displaystyle\varphi(A_{1})$
$\displaystyle=\varphi(A_{2})=\varphi(C_{2})=\varphi(C_{4})=\\{f\\}$
$\displaystyle\varphi(A_{3})$
$\displaystyle=\varphi(A_{4})=\varphi(C_{1})=\varphi(C_{3})=\emptyset$

Then $A_{1}{:}A_{2}\,{::}\,A_{3}{:}A_{4}$,
$C_{1}{:}C_{2}\,{::}\,C_{3}{:}C_{4}$, $A_{1}\sqsubseteq C_{1}$,
$A_{2}\sqsubseteq C_{2}$ and $A_{3}\sqsubseteq C_{3}$ are satisfied in
$\mathfrak{I}$, whereas $A_{4}\sqsubseteq C_{4}$ is not.

The following example shows that from $A_{1}{:}B_{1}\,{::}\,C_{1}{:}D_{1}$ and
$A_{2}{:}B_{2}\,{::}\,C_{2}{:}D_{2}$, in general we cannot infer $(A_{1}\sqcap
A_{2}){:}(B_{1}\sqcap B_{2})\,{::}\,(C_{1}\sqcap C_{2}){:}(D_{1}\sqcap
D_{2})$.

######  Example 7.

Consider a feature-enriched interpretation $\mathfrak{I}$ s.t.:

$\displaystyle\varphi(A_{1})=\varphi(A_{2})=\varphi(B_{1})=\varphi(C_{2})=\emptyset$
$\displaystyle\varphi(C_{1})=\varphi(D_{1})=\varphi(B_{2})=\varphi(D_{2})=\\{f\\}$

Then $A_{1}{:}B_{1}\,{::}\,C_{1}{:}D_{1}$ and
$A_{2}{:}B_{2}\,{::}\,C_{2}{:}D_{2}$ are satisfied in $\mathfrak{I}$, while
$(A_{1}\sqcap A_{2}){:}(B_{1}\sqcap B_{2})\,{::}\,(C_{1}\sqcap
C_{2}){:}(D_{1}\sqcap D_{2})$ is not, since

$\displaystyle\varphi(B_{1}\sqcap B_{2})\setminus\varphi(A_{1}\sqcap A_{2})$
$\displaystyle=\\{f\\}$ $\displaystyle\varphi(D_{1}\sqcap
D_{2})\setminus\varphi(C_{1}\sqcap C_{2})$ $\displaystyle=\emptyset$

### Counterexamples for Section 4.3

We show in the following counterexample that the condition
$B_{1}{\triangleright}B_{3}{::}B_{2}{\triangleright}B_{4}$ in Proposition 11
is indeed required.

######  Example 8.

Let
$\mathfrak{I}=(\mathcal{I},[\mathcal{F}_{1},\mathcal{F}_{2}],\mathcal{X},\pi,\sim,\mathcal{S})$
be a domain constrained interpretation, where $\mathcal{X}=\\{\mathcal{F}\\}$
and the sets of features $\mathcal{F}_{i}$ are defined as follows:

$\displaystyle\mathcal{F}_{1}$ $\displaystyle=\\{f\\}$
$\displaystyle\mathcal{F}_{2}$ $\displaystyle=\\{g\\}$

Now consider natural concepts $A_{1},A_{2},A_{3},A_{4},\allowbreak
B_{1},\allowbreak B_{2},\allowbreak B_{3},\allowbreak B_{4}$ with the
following feature assignments:

$\displaystyle\varphi(A_{1})$ $\displaystyle=\\{f\\}$
$\displaystyle\varphi(A_{2})$ $\displaystyle=\\{g\\}$
$\displaystyle\varphi(A_{3})$ $\displaystyle=\\{f\\}$
$\displaystyle\varphi(A_{4})$ $\displaystyle=\\{g\\}$
$\displaystyle\varphi(B_{1})$ $\displaystyle=\emptyset$
$\displaystyle\varphi(B_{2})$ $\displaystyle=\emptyset$
$\displaystyle\varphi(B_{3})$ $\displaystyle=\\{f\\}$
$\displaystyle\varphi(B_{4})$ $\displaystyle=\\{f\\}$

Furthermore, suppose $\sim=\\{1,2\\}\times\\{1,2\\}$ and $\sigma_{12}(f)=g$.
It is easy to verify that, apart from
$B_{1}{\triangleright}B_{3}{::}B_{2}{\triangleright}B_{4}$, the conditions
from Proposition 11 (i.e. the assertions in $K$) are all satisfied, whereas
the conclusion $A_{4}\sqsubseteq B_{4}$ is not satisfied.

### Counterexamples for Section 4.4

The next two examples show that $C$-transitivity is not satisfied under the
weak semantics, for standard analogy assertions and strong analogy assertions
respectively.

######  Example 9.

Let
$\mathfrak{I}=(\mathcal{I},[\mathcal{F}_{1},...,\mathcal{F}_{k}],\mathcal{X},\pi,\sim,\mathcal{S})$
be a weak domain constrained interpretation, where
$\mathcal{X}=\\{\mathcal{F}\\}$, $k=4$ and the sets of features
$\mathcal{F}_{i}$ are defined as follows:

$\displaystyle\mathcal{F}_{1}$ $\displaystyle=\\{a_{1},a_{1}^{\prime}\\}$
$\displaystyle\mathcal{F}_{2}$ $\displaystyle=\\{a_{2},a_{2}^{\prime}\\}$
$\displaystyle\mathcal{F}_{3}$ $\displaystyle=\\{a_{3},a_{3}^{\prime}\\}$
$\displaystyle\mathcal{F}_{4}$ $\displaystyle=\\{a_{4},a_{4}^{\prime}\\}$

Now consider natural concepts $A_{1},A_{2},A_{3},B_{1},B_{2},B_{3}$ with the
following feature assignments:

$\displaystyle\varphi(A_{1})$ $\displaystyle=\\{a_{1},a_{2}\\}$
$\displaystyle\varphi(A_{2})$ $\displaystyle=\\{a_{3},a_{4}\\}$
$\displaystyle\varphi(A_{3})$
$\displaystyle=\\{a_{1}^{\prime},a_{2}^{\prime}\\}$
$\displaystyle\varphi(A_{4})$ $\displaystyle=\\{a_{3},a_{4}\\}$
$\displaystyle\varphi(A_{5})$
$\displaystyle=\\{a^{\prime}_{1},a^{\prime}_{2}\\}$
$\displaystyle\varphi(A_{6})$
$\displaystyle=\\{a_{3}^{\prime},a_{4}^{\prime}\\}$

Furthermore, suppose $\sim=\\{1,2,3,4\\}\times\\{1,2,3,4\\}$. The different
bijections $\sigma_{(i,j)}$ are defined as follows:

In these diagrams, features from different domains $\mathcal{F}_{i}$ and
$\mathcal{F}_{j}$ are connected if they are mapped to each other by the
corresponding bijections $\sigma_{(i,j)}$ and $\sigma_{(j,i)}$. For instance,
according to these diagrams, we have $\sigma_{(1,4)}(a_{1})=a_{4}^{\prime}$.
We have that

$\displaystyle\mu(A_{1},A_{2})$
$\displaystyle=\\{\sigma_{\\{(1,3),(2,4)\\}}\\}$
$\displaystyle\mu(A_{2},A_{3})$
$\displaystyle=\\{\sigma_{\\{(3,2),(4,1)\\}}\\}$
$\displaystyle\mu(A_{4},A_{5})$
$\displaystyle=\\{\sigma_{\\{(3,2),(4,1)\\}}\\}$
$\displaystyle\mu(A_{5},A_{6})$
$\displaystyle=\\{\sigma_{\\{(1,3),(2,4)\\}}\\}$

from which we find that
$A_{2}{\triangleright}A_{3}{::}A_{4}{\triangleright}A_{5}$ and
$A_{1}{\triangleright}A_{2}{::}A_{5}{\triangleright}A_{6}$ are satisfied. On
the other hand, we have:

$\displaystyle\mu(A_{1},A_{3})=$
$\displaystyle\\{\sigma_{\\{(1,2),(2,1)\\}}\\}$
$\displaystyle\mu(A_{4},A_{6})=$
$\displaystyle\\{\sigma_{\\{(3,4),(4,3)\\}}\\}$

meaning that $A_{1}{\triangleright}A_{3}{::}A_{4}{\triangleright}A_{6}$ is not
satisfied.

######  Example 10.

Let
$\mathfrak{I}=(\mathcal{I},[\mathcal{F}_{1},...,\mathcal{F}_{k}],\mathcal{X},\pi,\sim,\mathcal{S})$
be a weak domain constrained interpretation, where
$\mathcal{X}=\\{\mathcal{F}\\}$, $k=4$ and the sets of features
$\mathcal{F}_{i}$ are defined as follows:

$\displaystyle\mathcal{F}_{1}$ $\displaystyle=\\{a_{1}\\}$
$\displaystyle\mathcal{F}_{2}$ $\displaystyle=\\{b_{1}\\}$
$\displaystyle\mathcal{F}_{3}$ $\displaystyle=\\{a_{2}\\}$
$\displaystyle\mathcal{F}_{4}$ $\displaystyle=\\{b_{2}\\}$

Now consider natural concepts $A_{1},A_{2},A_{3},A_{4},A_{5},A_{6}$ with the
following feature assignments:

$\displaystyle\varphi(A_{1})$ $\displaystyle=\\{a_{1},a_{2}\\}$
$\displaystyle\varphi(A_{2})$ $\displaystyle=\\{b_{1},b_{2}\\}$
$\displaystyle\varphi(A_{3})$ $\displaystyle=\\{a_{1},a_{2}\\}$
$\displaystyle\varphi(A_{4})$ $\displaystyle=\\{b_{1},b_{2}\\}$
$\displaystyle\varphi(A_{5})$ $\displaystyle=\\{a_{1},a_{2}\\}$
$\displaystyle\varphi(A_{6})$ $\displaystyle=\\{b_{1},b_{2}\\}$

Furthermore, suppose $\sim=\\{1,2,3,4\\}\times\\{1,2,3,4\\}$. The different
bijections $\sigma_{(i,j)}$ are uniquely defined, given that the domains are
singletons, e.g. we have $\sigma_{(1,2)}(a_{1})=b_{1}$. Then clearly we have
that $A_{2}{\blacktriangleright}A_{3}{::}B_{1}{\blacktriangleright}B_{2}$ and
$A_{1}{\blacktriangleright}A_{2}{::}A_{5}{\blacktriangleright}A_{6}$ are
satisfied, but
$A_{1}{\blacktriangleright}A_{3}{::}A_{4}{\blacktriangleright}A_{6}$ is not,
as

$\displaystyle\mu(A_{1},A_{3})=$
$\displaystyle\\{\sigma_{\emptyset},\sigma_{\\{(1,3),(3,1)\\}}\\}$
$\displaystyle\mu(B_{1},B_{3})=$
$\displaystyle\\{\sigma_{\emptyset},\sigma_{\\{(2,4),(4,2)\\}}\\}$

Next, we show that (16) is no longer valid for standard analogy assertions.

######  Example 11.

Let
$\mathfrak{I}=(\mathcal{I},[\mathcal{F}_{1},...,\mathcal{F}_{k}],\mathcal{X},\pi,\sim,\mathcal{S})$
be a weak domain constrained interpretation, where
$\mathcal{X}=\\{\mathcal{F}\\}$, $k=4$ and the sets of features
$\mathcal{F}_{i}$ are defined as follows:

$\displaystyle\mathcal{F}_{1}$
$\displaystyle=\\{a_{1},b_{1},c_{1},d_{1},e_{1}\\}$
$\displaystyle\mathcal{F}_{2}$
$\displaystyle=\\{a_{2},b_{2},c_{2},d_{2},e_{2}\\}$
$\displaystyle\mathcal{F}_{3}$
$\displaystyle=\\{a_{3},b_{3},c_{3},d_{3},e_{3}\\}$
$\displaystyle\mathcal{F}_{4}$
$\displaystyle=\\{a_{4},b_{4},c_{4},d_{4},e_{4}\\}$

Now consider natural concepts $A_{1},A_{2},B_{1},B_{2},C_{1},C_{2}$ with the
following feature assignments:

$\displaystyle\varphi(A_{1})$ $\displaystyle=\\{a_{1},a_{2}\\}$
$\displaystyle\varphi(A_{2})$ $\displaystyle=\\{a_{3},a_{4}\\}$
$\displaystyle\varphi(B_{1})$ $\displaystyle=\\{b_{1},b_{2}\\}$
$\displaystyle\varphi(B_{2})$ $\displaystyle=\\{b_{3},b_{4}\\}$
$\displaystyle\varphi(C_{1})$ $\displaystyle=\\{c_{1},c_{2}\\}$
$\displaystyle\varphi(C_{2})$ $\displaystyle=\\{c_{3},c_{4}\\}$

Furthermore, suppose $\sim=\\{1,2,3,4\\}\times\\{1,2,3,4\\}$. The different
bijections $\sigma_{(i,j)}$ are defined by the following diagrams:

It can now readily be verified that this interpretation satisfies
$A_{1}{\triangleright}A_{2}{::}B_{1}{\triangleright}B_{2}$, which is witnessed
by the domain translation $\sigma_{\\{(1,3),(2,4)\\}}$, and that this
interpretation also satisfies
$B_{1}{\triangleright}B_{2}{::}C_{1}{\triangleright}C_{2}$, which is witnessed
by the domain translation $\sigma_{\\{(1,4),(2,3)\\}}$. But there is no domain
translation that can witness
$A_{1}{\triangleright}A_{2}{::}C_{1}{\triangleright}C_{2}$.

Next we show that Proposition 9 is not valid for strong analogy assertions.

######  Example 12.

Let
$\mathfrak{I}=(\mathcal{I},[\mathcal{F}_{1},...,\mathcal{F}_{k}],\mathcal{X},\pi,\sim,\mathcal{S})$
be a weak domain constrained interpretation, where
$\mathcal{X}=\\{\mathcal{F}\\}$, $k=4$ and the sets of features
$\mathcal{F}_{i}$ are defined as follows:

$\displaystyle\mathcal{F}_{1}$
$\displaystyle=\\{a_{1},b_{1},c_{1},d_{1},e_{1}\\}$
$\displaystyle\mathcal{F}_{2}$
$\displaystyle=\\{a_{2},b_{2},c_{2},d_{2},e_{2}\\}$
$\displaystyle\mathcal{F}_{3}$
$\displaystyle=\\{a_{3},b_{3},c_{3},d_{3},e_{3}\\}$
$\displaystyle\mathcal{F}_{4}$
$\displaystyle=\\{a_{4},b_{4},c_{4},d_{4},e_{4}\\}$

Now consider natural concepts $A_{1},A_{2},B_{1},B_{2}$ with the following
feature assignments:

$\displaystyle\varphi(A_{1})$ $\displaystyle=\\{a_{1},a_{2}\\}$
$\displaystyle\varphi(A_{2})$ $\displaystyle=\\{a_{3},a_{4}\\}$
$\displaystyle\varphi(B_{1})$ $\displaystyle=\\{b_{1},b_{2}\\}$
$\displaystyle\varphi(B_{2})$ $\displaystyle=\\{b_{3},b_{4}\\}$

Furthermore, let $\kappa_{r}$ be defined such that

$\displaystyle\kappa_{r}(A_{1})$ $\displaystyle=\\{c_{1},c_{2}\\}$
$\displaystyle\kappa_{r}(A_{2})$ $\displaystyle=\\{c_{3},c_{4}\\}$
$\displaystyle\kappa_{r}(B_{1})$ $\displaystyle=\\{d_{1},d_{2}\\}$
$\displaystyle\kappa_{r}(B_{2})$ $\displaystyle=\\{d_{3},d_{4}\\}$

Furthermore, suppose $\sim=\\{1,2,3,4\\}\times\\{1,2,3,4\\}$. The different
bijections $\sigma_{(i,j)}$ are defined as follows:

Then we have that

$\displaystyle\mu(A_{1},A_{2})$
$\displaystyle=\mu(B_{1},B_{2})=\\{\sigma_{\\{(1,3),(2,4)\\}},\sigma_{\\{(1,4),(2,3)\\}}\\}$
$\displaystyle\mu(\exists r.A_{1},\exists r.A_{2})$
$\displaystyle=\\{\sigma_{\\{(1,3),(2,4)\\}},\sigma_{\\{(1,4),(2,3)\\}}\\}$
$\displaystyle\mu(\exists r.B_{1},\exists r.B_{2})$
$\displaystyle=\\{\sigma_{\\{(1,3),(2,4)\\}}\\}$

from which we find that
$A_{1}{\blacktriangleright}A_{2}{::}B_{1}{\blacktriangleright}B_{1}$ is
satisfied while $(\exists r.A_{1}){\blacktriangleright}(\exists
r.A_{2}){::}(\exists r.B_{1}){\blacktriangleright}(\exists r.B_{2})$ and
$A_{1}{\blacktriangleright}A_{2}{::}(\exists
r.B_{1}){\blacktriangleright}(\exists r.B_{2})$ are not.

The next example clarifies why Proposition 8 is not satisfied under the weak
semantics, neither for standard nor for strong analogy assertions.

######  Example 13.

Let
$\mathfrak{I}=(\mathcal{I},[\mathcal{F}_{1},...,\mathcal{F}_{k}],\mathcal{X},\pi,\sim,\mathcal{S})$
be a weak domain constrained interpretation, where
$\mathcal{X}=\\{\mathcal{F}\\}$, $k=2$ and the sets of features
$\mathcal{F}_{i}$ are defined as follows:

$\displaystyle\mathcal{F}_{1}$ $\displaystyle=\\{f\\}$
$\displaystyle\mathcal{F}_{2}$ $\displaystyle=\\{g\\}$

Now consider natural concepts $A_{1},\allowbreak A_{2},\allowbreak
A_{3},\allowbreak A_{4},\allowbreak B_{1},\allowbreak B_{2},\allowbreak
B_{3},\allowbreak B_{4}$ with the following feature assignments:

$\displaystyle\varphi(A_{1})$ $\displaystyle=\\{f\\}$
$\displaystyle\varphi(A_{2})$ $\displaystyle=\\{g\\}$
$\displaystyle\varphi(A_{3})$ $\displaystyle=\\{f\\}$
$\displaystyle\varphi(A_{4})$ $\displaystyle=\\{g\\}$
$\displaystyle\varphi(B_{1})$ $\displaystyle=\\{f\\}$
$\displaystyle\varphi(B_{2})$ $\displaystyle=\\{f\\}$
$\displaystyle\varphi(B_{3})$ $\displaystyle=\\{f\\}$
$\displaystyle\varphi(B_{4})$ $\displaystyle=\\{f\\}$

Let $\sim=\\{1,2\\}\times\\{1,2\\}$ and $\sigma_{(1,2)}(f)=g$. Then it is
clear that $A_{1}{\triangleright}A_{2}{::}A_{3}{\triangleright}A_{4}$,
$B_{1}{\triangleright}B_{2}{::}B_{3}{\triangleright}B_{4}$,
$A_{1}{\blacktriangleright}A_{2}{::}A_{3}{\blacktriangleright}A_{4}$ and
$B_{1}{\blacktriangleright}B_{2}{::}B_{3}{\blacktriangleright}B_{4}$ are all
satisfied, while $(A_{1}\sqcap B_{1}){\triangleright}(A_{2}\sqcap
B_{2}){::}(A_{3}\sqcap B_{3}){\triangleright}(A_{4}\sqcap B_{4})$ and
$(A_{1}\sqcap B_{1}){\blacktriangleright}(A_{2}\sqcap B_{2}){::}(A_{3}\sqcap
B_{3}){\blacktriangleright}(A_{4}\sqcap B_{4})$ are not.

Finally we show that (11) is not satisfied under the weak semantics.

######  Example 14.

Let
$\mathfrak{I}=(\mathcal{I},[\mathcal{F}_{1},...,\mathcal{F}_{k}],\mathcal{X},\pi,\sim,\mathcal{S})$
be a weak domain constrained interpretation, where
$\mathcal{X}=\\{\mathcal{F}\\}$, $k=2$ and the sets of features
$\mathcal{F}_{i}$ are defined as follows:

$\displaystyle\mathcal{F}_{1}$ $\displaystyle=\\{f\\}$
$\displaystyle\mathcal{F}_{2}$ $\displaystyle=\\{g\\}$

Now consider natural concepts $A_{1},\allowbreak A_{2},\allowbreak
A_{3},\allowbreak A_{4},\allowbreak B_{1},\allowbreak B_{2},\allowbreak
B_{3},\allowbreak B_{4}$ with the following feature assignments:

$\displaystyle\varphi(A_{1})$ $\displaystyle=\\{f,g\\}$
$\displaystyle\varphi(A_{2})$ $\displaystyle=\\{f,g\\}$
$\displaystyle\varphi(A_{3})$ $\displaystyle=\\{f\\}$
$\displaystyle\varphi(A_{4})$ $\displaystyle=\\{f\\}$
$\displaystyle\varphi(B_{1})$ $\displaystyle=\\{f\\}$
$\displaystyle\varphi(B_{2})$ $\displaystyle=\\{g\\}$
$\displaystyle\varphi(B_{3})$ $\displaystyle=\\{f\\}$
$\displaystyle\varphi(B_{4})$ $\displaystyle=\\{g\\}$

Let $\sim=\\{1,2\\}\times\\{1,2\\}$ and $\sigma_{(1,2)}(f)=g$. Then it is
clear that $A_{1}{\triangleright}A_{2}{::}A_{3}{\triangleright}A_{4}$,
$B_{1}{\triangleright}B_{2}{::}B_{3}{\triangleright}B_{4}$,
$B_{1}{\triangleright}B_{3}{::}B_{2}{\triangleright}B_{4}$,
$A_{1}{\blacktriangleright}A_{2}{::}A_{3}{\blacktriangleright}A_{4}$,
$B_{1}{\blacktriangleright}B_{2}{::}B_{3}{\blacktriangleright}B_{4}$ and
$B_{1}{\blacktriangleright}B_{3}{::}B_{2}{\blacktriangleright}B_{4}$ are all
satisfied, as well as $A_{1}\sqsubseteq B_{1}$, $A_{2}\sqsubseteq B_{2}$ and
$A_{3}\sqsubseteq B_{3}$. However, $A_{4}\sqsubseteq B_{4}$ is not satisfied.

## References

  * Baader et al. [2017] Franz Baader, Ian Horrocks, Carsten Lutz, and Ulrike Sattler.  An Introduction to Description Logic.  Cambridge University Press, 2017.
  * Balazevic et al. [2019] Ivana Balazevic, Carl Allen, and Timothy M. Hospedales.  Tucker: Tensor factorization for knowledge graph completion.  In Proceedings EMNLP, pages 5184–5193, 2019.
  * Barbot et al. [2019] Nelly Barbot, Laurent Miclet, and Henri Prade.  Analogy between concepts.  Artificial Intelligence, 275:487–539, 2019.
  * Bayoudh et al. [2007] Sabri Bayoudh, Laurent Miclet, and Arnaud Delhay.  Learning by analogy: A classification rule for binary and nominal data.  In Proceedings IJCAI, pages 678–683, 2007.
  * Beltagy et al. [2013] Islam Beltagy, Cuong Chau, Gemma Boleda, Dan Garrette, Katrin Erk, and Raymond Mooney.  Montague meets Markov: Deep semantics with probabilistic logical form.  In Proceedings of *SEM, pages 11–21, 2013.
  * Bordes et al. [2013] A. Bordes, N. Usunier, A. Garcia-Duran, J. Weston, and O. Yakhnenko.  Translating embeddings for modeling multi-relational data.  In Proc. of NIPS, pages 2787–2795. 2013.
  * Bouraoui and Schockaert [2019] Zied Bouraoui and Steven Schockaert.  Automated rule base completion as bayesian concept induction.  In Proceedings AAAI, pages 6228–6235, 2019.
  * Brown et al. [2020] Tom B. Brown, Benjamin Mann, et al.  Language models are few-shot learners.  In Proceedings NeurIPS, 2020.
  * d’Amato et al. [2006] Claudia d’Amato, Nicola Fanizzi, and Floriana Esposito.  Analogical reasoning in description logics.  In Proceedings of the Second ISWC Workshop on Uncertainty Reasoning for the Semantic Web, 2006.
  * Gentner [1983] Dedre Gentner.  Structure-mapping: A theoretical framework for analogy.  Cognitive science, 7(2):155–170, 1983.
  * Hofstadter et al. [1995] Douglas R Hofstadter, Melanie Mitchell, et al.  The copycat project: A model of mental fluidity and analogy-making.  Advances in Connectionist and Neural Computation Theory, 2:205–267, 1995.
  * Holyoak and Thagard [1997] Keith J Holyoak and Paul Thagard.  The analogical mind.  American psychologist, 52(1):35–44, 1997.
  * Hug et al. [2016] Nicolas Hug, Henri Prade, Gilles Richard, and Mathieu Serrurier.  Analogical classifiers: A theoretical perspective.  In Proceedings ECAI, pages 689–697, 2016.
  * Ibáñez-García et al. [2020] Yazmín Ibáñez-García, Víctor Gutiérrez-Basulto, and Steven Schockaert.  Plausible reasoning about el-ontologies using concept interpolation.  In Proceedings KR, pages 506–516, 2020.
  * Medina et al. [2004] Jesús Medina, Manuel Ojeda-Aciego, and Peter Vojtás.  Similarity-based unification: a multi-adjoint approach.  Fuzzy Sets and Systems, 146(1):43 – 62, 2004.
  * Mikolov et al. [2013] Tomas Mikolov, Wen-tau Yih, and Geoffrey Zweig.  Linguistic regularities in continuous space word representations.  In Proceedings NAACL-HLT, pages 746–751, 2013.
  * Prade and Richard [2013] Henri Prade and Gilles Richard.  From analogical proportion to logical proportions.  Logica Universalis, 7(4):441–505, 2013.
  * Prade and Richard [2014] Henri Prade and Gilles Richard.  From analogical proportion to logical proportions: A survey.  In Computational Approaches to Analogical Reasoning: Current Trends, pages 217–244. 2014.
  * Rocktäschel and Riedel [2017] Tim Rocktäschel and Sebastian Riedel.  End-to-end differentiable proving.  In Proc. NIPS, pages 3791–3803, 2017.
  * Trouillon et al. [2017] Théo Trouillon, Christopher R. Dance, Éric Gaussier, Johannes Welbl, Sebastian Riedel, and Guillaume Bouchard.  Knowledge graph completion via complex tensor factorization.  J. Mach. Learn. Res., 18:130:1–130:38, 2017.
  * Turney [2006] Peter D. Turney.  Similarity of semantic relations.  Comput. Linguistics, 32(3):379–416, 2006.
  * Tversky [1977] Amos Tversky.  Features of similarity.  Psychological Review, 84(4):327–352, 1977.
  * Yang et al. [2015] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng.  Embedding entities and relations for learning and inference in knowledge bases.  In Proceedings ICLR, 2015.