11institutetext:  1Conservatoire National des Arts et Métiers
2Léonard de Vinci Pôle Universitaire, Research Center

# Parameterisation of Reasoning on Temporal Markov Logic Networks

Victor David1 Raphaël Fournier-S’niehotta 1 Nicolas Travers1,2

###### Abstract

We aim at improving reasoning on inconsistent and uncertain data. We focus on
knowledge-graph data, extended with time intervals to specify their validity,
as regularly found in historical sciences. We propose principles on semantics
for efficient Maximum A-Posteriori inference on the new Temporal Markov Logic
Networks (TMLN) which extend the Markov Logic Networks (MLN) by uncertain
temporal facts and rules. We examine total and partial temporal
(in)consistency relations between sets of temporal formulae. Then we propose a
new Temporal Parametric Semantics, which may combine several sub-functions,
allowing to use different assessment strategies. Finally, we expose the
constraints that semantics must respect to satisfy our principles.

###### Keywords:

Temporal Markov Logic Networks Temporal Maximum A-Posteriori Inference
Temporal Parametric Semantics.

##  1 Introduction

Reasoning on large data sets to extend knowledge is an open challenge [3, 8,
13, 11]. Most approaches model information with Knowledge Graphs (KGs) [7],
and rely on Ontologies [14], Machine Learning [20] or Neural Networks [12]
representations. Then, Description Logic [10] and Temporal Logic [18] are used
for rules satisfiability.

For historians, reasoning under uncertainty and inconsistency is at the basis
of methodology: the validity of any fact remains questionable. Temporal
information is crucial: outside of a temporal interval, a fact becomes false.
Using facts, temporal and uncertainty information, a historian may obtain
several consistent levels of knowledge.

Recent works on KG reasoning do not focus on both time and uncertainty.
Several models with Markov Logic Networks (MLN) have been proposed [5, 17].
One focused on reasoning on Uncertain Temporal Knowledge Graphs (UTKG) with
specific temporal inference rules [4]. However, those representations cannot
handle a fully uncertain universe where any fact or rule may be uncertain.

We propose to generalize this approach, by i) introducing a new representation
of knowledge, called _temporal MLN_ (TMLN), built on (a temporal) many-sorted
logic, for reasoning on both time and uncertainty, ii) enlarging the notion of
uncertainty to rules, and iii) adapting reasoning, to deal with both uncertain
facts and rules. We define a new temporal semantics and a temporal extension
to Maximum A-Posteriori (MAP) inference [16]. This MAP inference produces
_instantiations_ , i.e.,  extended sets of facts maximizing the score w.r.t. a
temporal semantics. Finally, we generalise the temporal semantics by a
Parametric Semantics, which may combine several sub-functions for various
consistency validations.

##  2 Background

In a seminal work [4], Chekol et al. formalise the UTKG approach, which
integrates both time and uncertainty in Knowledge Graphs to reach a certain
world maximisation. However, they do not take into account the possibility to
have uncertain rules. We put _time_ at the heart of reasoning, and enlarge
their vision. Firstly, we formalise the notion of temporal uncertainty, by
combining certain and uncertain formulae. Secondly, our novel representation
of TMLN allows for easier manipulations and better analyses.

###  2.1 Many-Sorted First Order Logic

We start by presenting what is a Many-Sorted First-Order Logic (introduced in
[19]).

######  Definition 1 (Many-Sorted FOL)

Let ${\mathbf{S}}{\mathbf{o}}=\\{s_{1},\dots,s_{n}\\}$ be a set of sorts. A
Many-Sorted First-Order Logic $\mathtt{MS}$-$\mathtt{FOL}$, is a set of
formulae built up by induction from: a set
${\mathbf{C}}=\\{a_{1},\ldots,a_{l}\\}$ of constants, a set
${\mathbf{V}}=\\{x^{s},y^{s},z^{s},\ldots\mid s\in{\mathbf{S}}{\mathbf{o}}\\}$
of variables, a set ${\mathbf{P}}=\\{P_{1},\ldots,P_{m}\\}$ of predicates, a
function $\mathtt{ar}:{\mathbf{P}}\rightarrow\mathbb{N}$ which tells the arity
of any predicate, a function $\mathtt{sort}$ s.t. for $P\in{\mathbf{P}}$,
$\mathtt{sort}(P)\in{\mathbf{S}}{\mathbf{o}}^{\mathtt{ar}(P)}$, and for
$c\in{\mathbf{C}}$, $\mathtt{sort}(c)\in{\mathbf{S}}{\mathbf{o}}$, the usual
connectives ($\neg$, $\vee$, $\wedge$, $\rightarrow$, $\leftrightarrow$),
Boolean constants ($\top$ and $\bot$) and quantifier symbols
($\forall,\exists$). A ground formula is a formula without any variable.

Lowercase (resp. uppercase) greek letters like $\phi,\psi$ (resp. $\Phi,\Psi$)
denote formulae (resp. sets of formulae). $\mathtt{MS}$-$\mathtt{FOL}$ is the
set of all formulae.

###### Example 1

For instance let ${\mathbf{S}}{\mathbf{o}}=\\{s_{1},s_{2}\\}$, let
$P_{1}\in{\mathbf{P}}$ such that $\mathtt{sort}(P_{1})=s_{2}\times s_{1}\times
s_{1}$, let $a_{1},a_{2},t_{1},t_{2}\in{\mathbf{C}}$ such that
$\mathtt{sort}(a_{1})=\mathtt{sort}(a_{2})=s_{2}$,
$\mathtt{sort}(t_{1})=\mathtt{sort}(t_{2})=s_{1}$ and let
$x^{s_{2}}\in{\mathbf{V}}$. We can build then the following
$\mathtt{MS}$-$\mathtt{FOL}$ formulae: $P_{1}(a_{1},t_{1},t_{2})$, $\forall
x^{s_{2}}P_{1}(x^{s_{2}},t_{1},t_{2})$. However, $P_{1}(t_{1},t_{2},a_{1})$ or
$\forall x^{s_{2}}P_{1}(a_{1},a_{2},x^{s_{2}})$ cannot be built because they
do not respect the sorts.

$\mathtt{MS}$-$\mathtt{FOL}$ formulae are evaluated via a notion of structure
called $n$-sorted structures [9]. Classical first-order logic formulae are
captured as $1$-sorted structures.

######  Definition 2 (Structure)

A $n$-sorted structure is
${\mathbf{S}}{\mathbf{t}}=(\\{D_{1},\ldots,D_{n}\\},\\{R_{1},\ldots,R_{m}\\},\linebreak\\{c_{1},\ldots,c_{l}\\})$,
where $D_{1},\ldots,D_{n}$ are the (non-empty) domains, $R_{1},\ldots,R_{m}$
are relations between domains’ elements, and $c_{1},\ldots,c_{l}$ are distinct
constants in the domains.

Our running example is presented in Example 2. These sentences gather
biographical elements about a French philosopher from the 14th century, Nicole
Oresme.

###### Example 2

Nicole Oresme was a person and a philosopher born in the Middle Ages between
1320-1382. It would appear that Nicole Oresme attended the College of Navarre
around 1340-1354 and more likely around 1355-1360. Nicole Oresme possibly did
not attend the College of Navarre around 1353-1370. Sometimes, a person who
lived in Middle Ages and studied at College of Navarre came from a peasant
family. Usually, a philosopher born in the Middle Ages did not come from a
peasant family.

In $\mathtt{MS}$-$\mathtt{FOL}$, though without uncertainty, we may then
define a suitable structure.

###### Example 3

An example of structure associated with the $\mathtt{MS}$-$\mathtt{FOL}$ from
Example 2 is ${\mathbf{S}}{\mathbf{t}}_{hist}$ = $(\\{Time,Concept\\},$
$\\{Person,Philosopher,LivePeriod,PeasantFamily,\linebreak Studied\\},$
$\\{t_{min},1300,1301,1302,\ldots,1400,t_{max},NO,MA,CoN\\})$, in which:

  * •

$Time$ is the set of time points, corresponding to the sort $s_{1}$ and
$Concept$ is the set of all non-temporal objects, corresponding to the sort
$s_{2}$,

  * •

$Person,Philosopher,LivePeriod$, etc. are the predicate symbols’ relations
(e.g., $Person\subseteq Concept\times Time\times Time$ indicates which
elements are a person).

  * •

$t_{min}$, 1300, 1301, $\ldots$, 1400, $t_{max}$ are elements of the domain
$Time$ associated with the sort $s_{1}$, while $NO$ (Nicolas Oresme), $MA$
(Middle Ages) and $CoN$ (College of Navarre) are elements of the domain
$Concept$ associated with the sort $s_{2}$.

Now, we show how $\mathtt{MS}$-$\mathtt{FOL}$ formulae are _interpreted_.

######  Definition 3 (Interpretation)

An interpretation ${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}$ over a structure
${\mathbf{S}}{\mathbf{t}}$ assigns to elements of the
$\mathtt{MS}$-$\mathtt{FOL}$ vocabulary some values in the structure
${\mathbf{S}}{\mathbf{t}}$. Formally,
– ${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}(s_{i})=D_{i}$, for
$i\in\\{1,\dots,n\\}$ (each sort symbol is assigned to a domain),
– ${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}(P_{i})=R_{i}$, for
$i\in\\{1,\dots,m\\}$ (each predicate symbol is assigned to a relation),
– ${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}(a_{i})=c_{i}$, for
$i\in\\{1,\dots,l\\}$ (each constant symbol is assigned to a value).
Then, satisfying formulae is recursively defined by:
– ${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}\models P_{i}(a_{1},\dots,a_{k})$
iff
$({\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}(a_{1}),\dots,{\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}(a_{k}))\in
R_{i}$,
– ${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}\models\exists x^{s_{i}}\phi$ iff
${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}},x^{s_{i}}\leftarrow v}\models\phi$ for
some $v\in D_{i}$,
– ${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}\models\forall x^{s_{i}}\phi$ iff
${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}},x^{s_{i}}\leftarrow v}\models\phi$ for
each $v\in D_{i}$,
– ${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}\models\phi\wedge\psi$ iff
${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}\models\phi$ and
${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}\models\psi$,
– ${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}\models\phi\vee\psi$ iff
${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}\models\phi$ or
${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}\models\psi$,
– ${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}\models\neg\phi$ iff
${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}\not\models\phi$.
where ${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}},x^{s_{i}}\leftarrow v}$ is a
modified version of ${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}$ s.t. the
variable $x^{s_{i}}$ is replaced by a value $v$ in the domain $D_{i}$
corresponding to the sort symbol $s_{i}$. Finally, if $\Phi$ is a set of
formulae, then ${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}\models\Phi$ iff
${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}\models\phi$ for each $\phi\in\Phi$.

Definition 3 does not target the satisfaction of implications and
equivalences, while they can be defined by:
$(\phi\rightarrow\psi)\equiv(\neg\phi\vee\psi)$, and
$(\phi\leftrightarrow\psi)\equiv(\phi\rightarrow\psi)\wedge(\psi\rightarrow\phi)$.
For instance, the set of interpretations of the formula $P(a)\vee P(b)$ is
equal to $\\{\\{P(a)\\},\\{P(b)\\},\\{P(a),P(b)\\}\\}$ and for $P(a)\wedge
P(b)$ is $\\{\\{P(a),P(b)\\}\\}$.

With these notions of structures and interpretations on TMLNs, we may define
the consequence relations and logical consequences over
$\mathtt{MS}$-$\mathtt{FOL}$ formulae.

######  Definition 4 (Consequence Relation)

Let $\phi$ and $\psi$ be two $\mathtt{MS}$-$\mathtt{FOL}$ formulae. We say
that $\psi$ is a consequence of $\phi$, denoted by $\phi\vdash\psi$, if for
any structure ${\mathbf{S}}{\mathbf{t}}$, and any interpretation
${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}$ over ${\mathbf{S}}{\mathbf{t}}$,
${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}\models\phi$ implies
${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}\models\psi$.

######  Definition 5 (Logical Consequences - ${\mathtt{Cn}}$)

Let $\phi\in\mathtt{MS}$-$\mathtt{FOL}$. The function ${\mathtt{Cn}}(\phi)$ is
the set of all logical consequences of $\phi$, i.e.
${\mathtt{Cn}}(\phi)=\\{\psi\in\mathtt{MS}$-$\mathtt{FOL}\ |\
\phi\vdash\psi\\}.$

The function ${\mathtt{Cn}}$ returns an infinite set of formulae, but for
clarity we consider only one formula per equivalent class and only the
predicates and constants appearing in the original formulae. Such as,
${\mathtt{Cn}}(P(a)\vee P(b))=\\{P(a)\vee P(b)\\}$ and
${\mathtt{Cn}}(P(a)\wedge P(b))=\\{P(a),P(b),P(a)\wedge P(b),P(a)\vee
P(b)\\}\\}$.

##  3 Temporal and Uncertain Knowledge Representation

Markov Logic Networks (MLNs) combine Markov Networks and First-Order Logic
(FOL) by attaching weights to ﬁrst-order formulae and treating them as feature
templates for Markov Networks [15]. We extend this framework to temporal
information by resorting to Many-Sorted First-Order Logic
($\mathtt{MS}$-$\mathtt{FOL}$).

###  3.1 Temporal Markov Logic Networks

Let start by defining what we call a Temporal Many-Sorted First-Order Logic
$\mathtt{TS}$-$\mathtt{FOL}$.

######  Definition 6 (Temporal Many-Sorted FOL)

A $\mathtt{TS}$-$\mathtt{FOL}$ evaluated by a structure
${\mathbf{S}}{\mathbf{t}}$ is a constrained $\mathtt{MS}$-$\mathtt{FOL}$ where
$|{\mathbf{S}}{\mathbf{o}}|\geq 2$, for any interpretation
${\mathbf{I}}_{{\mathbf{S}}{\mathbf{t}}}(s_{1})=Time$, any predicate
$P_{i}\in\mathtt{TS}$-$\mathtt{FOL}$ has $\mathtt{ar}(P_{i})\geq 3$ with the
sort of the last two parameters belonging to $s_{1}$ and $t_{min}$ and
$t_{max}$ are time constants indicating the minimum and maximum time points
for any pre-order between the time constants.

Using this constrained $\mathtt{MS}$-$\mathtt{FOL}$ accompanied with a
temporal domain (named $Time$) and temporal predicates (the last two
parameters indicate the validity temporal bounds), we may represent temporal
facts and rules. Finally, Temporal Markov Logic Networks (TMLN) extend
$\mathtt{TS}$-$\mathtt{FOL}$ (resp. Markov Logic Networks) by associating a
degree of certainty to each formula (resp. by adding a temporal validity to
the predicates).

######  Definition 7 (TMLN)

A Temporal Markov Logic Network ${\mathbf{M}}=({\mathbf{F}},{\mathbf{R}})$,
based on a $\mathtt{TS}$-$\mathtt{FOL}$, is a set of weighted temporal facts
and rules where ${\mathbf{F}}$ and ${\mathbf{R}}$ are sets of pairs such that:
– ${\mathbf{F}}=\\{(\phi_{1},w_{1}),$…$,(\phi_{n},w_{n})\\}$ with $\forall
i\in\\{1,$…$,n\\}$, $\phi_{i}\in\mathtt{TS}$-$\mathtt{FOL}$ such that it is a
ground formula and $w_{i}\in[0,1]$,
–
${\mathbf{R}}=\\{(\phi^{\prime}_{1},w^{\prime}_{1}),$…$,(\phi^{\prime}_{k},w^{\prime}_{k})\\}$
with $\forall i\in\\{1,$…$,k\\}$,
$\phi^{\prime}_{i}\in\mathtt{TS}$-$\mathtt{FOL}$ such that it is not a ground
formula and in the form (premises,conclusion), i.e.,
$(\psi_{1}\wedge$…$\wedge\psi_{l})\rightarrow\psi_{l+1}$ where $\forall
j\in\\{1,$…$,l+1\\}$, $\psi_{j}\in\mathtt{TS}$-$\mathtt{FOL}$, and
$w_{i}\in[0,1]$.
The universe of all TMLNs is denoted by $\mathtt{TMLN}$.

$F_{1}$ | $(Person(NO,1320,1382)$ |  | $,\textbf{1})$
---|---|---|---
$F_{2}$ | $(Philosopher(NO,1320,1382)$ |  | $,\textbf{1})$
$F_{3}$ | $(LivePeriod(NO,MA,1320,1382)$ |  | $,\textbf{1})$
$F_{4}$ | $(Studied(NO,CoN,1340,1354)$ |  | $,\textbf{0.4})$
$F_{5}$ | $(Studied(NO,CoN,1355,1360)$ | $,\textbf{0.7})$
$F_{6}$ | $(\neg Studied(NO,CoN,1353,1370)$ | $,\textbf{0.5})$
$R_{1}$ | $(\forall x^{s_{2}},t_{1}^{s_{1}},t_{1}^{\prime s_{1}},t_{2}^{s_{1}},t_{2}^{\prime s_{1}},t_{3}^{s_{1}},t_{3}^{\prime s_{1}},(Person(x^{s_{2}},t_{1}^{s_{1}},t_{1}^{\prime s_{1}})\wedge LivePeriod(x^{s_{2}},MA,t_{2}^{s_{1}},t_{2}^{\prime s_{1}})\wedge$ |
|  $Studied(x^{s_{2}},CoN,t_{3}^{s_{1}},t_{3}^{\prime s_{1}}))\rightarrow PeasantFamily(x^{s_{2}},t_{min},t_{max})$ |  | $,\textbf{0.5})$
$R_{2}$ | $(\forall x^{s_{2}},t_{1}^{s_{1}},t_{1}^{\prime s_{1}},t_{2}^{s_{1}},t_{2}^{\prime s_{1}},(Philosopher(x^{s_{2}},t_{1}^{s_{1}},t_{1}^{\prime s_{1}})\wedge LivePeriod(x^{s_{2}},MA,t_{2}^{s_{1}},t_{2}^{\prime s_{1}}))$ |  |
|  $\rightarrow\neg PeasantFamily(x^{s_{2}},t_{min},t_{max})$ |  | $,\textbf{0.8})$
Table 1: Example of a TMLN for Nicole Oresme. $GR_{11}=((Person(NO,1320,1382)\wedge LivePeriod(NO,MA,1320,1382)\wedge$ |
---|---
$Studied(NO,CoN,1340,1354))$ $\rightarrow PeasantFamily(NO,t_{min},t_{max})$ |  , 0.4)
$GR_{12}=((Person(NO,1320,1382)\wedge LivePeriod(NO,MA,1320,1382)\wedge$ |
$Studied(NO,CoN,1355,1360))$ $\rightarrow PeasantFamily(NO,t_{min},t_{max})$ |  , 0.5)
$GR_{2}=((Philosopher(NO,1320,1382)\wedge LivePeriod(NO,MA,1320,1382))$ |
$\rightarrow\neg PeasantFamily(NO,t_{min},t_{max})$ |  , 0.8)
Table 2: Ground Rules Instantiating $R_{1}$ and $R_{2}$ (from Table 1) for
Nicole Oresme.

In the rest of the paper, we simplify the example by directly using the
structure defined in Example 3 (c.f. Section 2.1).

  * Example 2 (Continued). The TMLN representation of our running example can be found in Table 1. We may identify 6 independent facts and 2 rules, each one with temporal validity and certainty weights (arbitrary extracted from Example 2).

In order to select what is the most probable and consistent set of ground
formulae with a MAP inference, we need first to have our data (facts and
rules) represented in a TMLN. Then, we must obtain the ground rules (if
possible), by replacing the variables in the rules by constants (according to
our TMLN). We call this second step the instantiation.

###  3.2 TMLN Instantiation

Let ${\mathbf{M}}$ be a TMLN, we denote by $\mathtt{MI}({\mathbf{M}})$ the
Maximal TMLN Instantiation of ${\mathbf{M}}$. $\mathtt{MI}({\mathbf{M}})$
contains the set of ${\mathbf{M}}$’s facts and all ground rules that can be
constructed by instantiating all its predicates containing variables by other
deductible ground predicates (with logical consequence, from Definitions 4 and
5). A ground rule’s weight is the minimum of the weights of the formulae in
${\mathbf{M}}$ used to construct the instantiated rule.

Formally, to define the set of instantiations, we have to define two useful
notions. Firstly, we denote by
$\mathtt{TF}({\mathbf{M}})=\bigcup\limits_{(\phi,w)\in{\mathbf{M}}}\phi$ the
set of temporal formulae of ${\mathbf{M}}\in\mathtt{TMLN}$. Secondly, we
define the function
$\mathtt{W}:\mathtt{TS}$-$\mathtt{FOL}\times\mathtt{TMLN}\rightarrow[0,1]$,
returning the maximal weight of a temporal formula deductible from a TMLN:
$\mathtt{W}(\phi,{\mathbf{M}})=\mathtt{max}(\mathtt{min_{w}}({\mathbf{M}}_{1}),\ldots,\linebreak\mathtt{min_{w}}({\mathbf{M}}_{m}))$
s.t.
$\\{{\mathbf{M}}_{1},\ldots,{\mathbf{M}}_{m}\\}=\\{{\mathbf{M}}_{i}\subseteq{\mathbf{M}}\mid\mathtt{TF}({\mathbf{M}}_{i})\vdash\phi\text{
and }\nexists{\mathbf{M}}^{\prime}_{i}\subset{\mathbf{M}}_{i}\text{ s.t.
}\linebreak\mathtt{TF}({\mathbf{M}}^{\prime}_{i})\vdash\phi\\}$ and
$\mathtt{min_{w}}({\mathbf{M}}_{i}=\\{(\psi_{1},w_{1}),\ldots,(\psi_{l},w_{l})\\})=\mathtt{min}(w_{1},\ldots,w_{l})$.

######  Definition 8 (TMLN Instantiation)

Given ${\mathbf{M}}=({\mathbf{F}},{\mathbf{R}})\in\mathtt{TMLN}$, the set of
instantiations $\mathtt{MI}$ of ${\mathbf{M}}$ is defined as follows:

$\mathtt{MI}({\mathbf{M}})={\mathbf{F}}~{}~{}\cup\\{\big{(}(\phi_{1}\wedge\ldots\wedge\phi_{k}\rightarrow\phi_{k+1})_{X\leftarrow
C},w^{\prime}\big{)}\mid(\phi_{1}\wedge\ldots\wedge\phi_{k}\rightarrow\phi_{k+1},w)\in{\mathbf{R}},X=\\{x_{1},\ldots,x_{n}\\}\text{
is the set of }\text{variables in
}\phi_{1}\wedge\ldots\wedge\phi_{k}\rightarrow\phi_{k+1},C=\langle
c_{1},\ldots,c_{n}\rangle\text{ is a vector of constants replacing each
occurrence of the variables, }\\\ X^{\prime}_{i}\subseteq X\text{ is the set
of variables in }\phi_{i},C^{\prime}_{i}\subseteq C\text{ is the vector of
constants replaced in }\phi_{i}\\\ \text{ and the instantiated rule satisfies
the 2 following conditions:}$

1\. $\forall\phi_{i}\in\\{\phi_{1},\ldots,\phi_{k}\\}$,
$\phi_{iX^{\prime}_{i}\leftarrow
C^{\prime}_{i}}\in{\mathtt{Cn}}(\mathtt{TF}({\mathbf{M}}))$

2\. $w^{\prime}=\mathtt{min}(w,\mathtt{W}(\phi_{1X^{\prime}_{1}\leftarrow
C^{\prime}_{1}},{\mathbf{M}}),\ldots,\mathtt{W}(\phi_{kX^{\prime}_{k}\leftarrow
C^{\prime}_{k}},{\mathbf{M}})\\}$
Where $\phi_{X\leftarrow C}$ is the formula $\phi$ s.t. all the occurrences of
the variable $x_{i}\in X$ are replaced by the constant $c_{i}\in C$.

Currently, we only deal with universal (i.e., $\forall$) rules and no
existential one (i.e., $\exists$), to simplify the maximal TMLN instantiation.
Indeed, with existential rules, we would have to deal with a set of sets of
instantiations, given that we would not know which set of instantiations would
be true. We keep this question for future works.

From Example 2, the instantiation of $R_{1}$ (resp. $R_{2}$) are $GR_{11}$
(from $F_{1}$, $F_{3}$ and $F_{4}$) and $GR_{12}$ (from $F_{1}$, $F_{3}$ and
$F_{5}$) (resp. $GR_{2}$ from $F_{2}$ and $F_{3}$). Hence $GR_{11}$ has a
weight of $0.4$, $GR_{12}$ of $0.5$ and $GR_{2}$ of $0.8$, see Table 2.

A TMLN instantiation $I\subseteq\mathtt{MI}({\mathbf{M}})$ is a TMLN only
composed of ground formulae, $I$ is also called a state of the TMLN
${\mathbf{M}}$. The universe of all TMLN instantiations is denoted by
$\mathtt{TMLN}^{*}$. Note that an instantiation can be inconsistent. In our
example, $GR_{11},F_{1},F_{3},F_{4}$ imply $PeasantFamily(NO,t_{min},t_{max})$
while $GR_{2},F_{2},F_{3}$ imply $\neg PeasantFamily(NO,t_{min},t_{max})$,
i.e., they are inconsistent together. Thus, to obtain the most consistent and
informative set of instantiations, we have to compute the Maximum A-Posteriori
(MAP) inference [4, 16].

##  4 Temporal and Uncertain Knowledge Reasoning

Computing the MAP inference means “finding the most probable state of the
world” [4]. In order to do that, we integrate semantics on TMLN, before
examining principles governing those semantics and (in)consistency relations.

###  4.1 Temporal MAP Inference

Semantics are methods which compute the strength of a TMLN state. We denote
the universe of all semantics by $\mathtt{Sem}$, such that for any
${\mathcal{S}}\in\mathtt{Sem}$,
${\mathcal{S}}:\mathtt{TMLN^{*}}\rightarrow[0,+\infty[.$ We compute a strength
above 0, instead of a probability between 0 and 1. One semantics may maximise
the amount of information, while another may maximise the quality.

Temporal Maximum A-Posteriori (MAP) Inference in TMLN returns the most
probable, temporally consistent, and expanded state w.r.t. a given semantics.
Given ${\mathbf{M}}\in\mathtt{TMLN}$ and ${\mathcal{S}}\in\mathtt{Sem}$, a
method solving a MAP problem is denoted by:
$\mathtt{map}:\mathtt{TMLN}\times\mathtt{Sem}\rightarrow{\mathcal{P}}(\mathtt{TMLN^{*}})$,
where ${\mathcal{P}}(X)$ denote the powerset of X, such that:

$\mathtt{map}({\mathbf{M}},{\mathcal{S}})=\\{I\mid
I\in\underset{I~{}\subseteq~{}\mathtt{MI}({\mathbf{M}})}{\text{argmax}}~{}{\mathcal{S}}(I)\text{
and }\nexists
I^{\prime}\in\underset{I^{\prime}~{}\subseteq~{}\mathtt{MI}({\mathbf{M}})}{\text{argmax}}~{}{\mathcal{S}}(I^{\prime})\text{
s.t. }I\subset I^{\prime}\\}$.

To determine a MAP inference we need to define semantics, however not all
methods are desirable. Below we present some principles that a semantics
should satisfy.

###  4.2 Principles for semantics in Temporal MAP Inference

Our first principle states that adding new weightless information does not
change the strength of the MAPs of a TMLN, whatever the temporality is. Given
that the same set of predicates or formulae instantiated on different
temporalities are not equivalent, we homogenises $\mathtt{TS}$-$\mathtt{FOL}$
with the maximal time interval to define the information novelty.

For time homogenization, we denote by
$\scalebox{1.2}{$\tau$}:{\mathcal{P}}(\mathtt{TS}$-$\mathtt{FOL})\rightarrow{\mathcal{P}}(\mathtt{TS}$-$\mathtt{FOL})$,
the function transforming any temporal predicate into the maximal time
interval ($t_{min}$ and $t_{max}$).

######  Principle 1 (Temporal Neutrality)

Let ${\mathbf{M}}\in\mathtt{TMLN}$,
${\mathbf{M}}^{\prime}={\mathbf{M}}\cup\\{(\phi,w)\\}$ where $(\phi,w)$ is a
weighted temporal formula ($\phi\in\mathtt{TS}$-$\mathtt{FOL}$ and
$w\in[0,1]$), such that:

–
$\scalebox{1.2}{$\tau$}(\mathtt{TF}({\mathbf{M}}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi\\})$,
and

– $w=0$.

A semantics ${\mathcal{S}}\in\mathtt{Sem}$ satisfies temporal neutrality iff,
$\forall I\in\mathtt{map}({\mathbf{M}},{\mathcal{S}})$ and $\forall
I^{\prime}\in\mathtt{map}({\mathbf{M}}^{\prime},{\mathcal{S}})$,
${\mathcal{S}}(I)={\mathcal{S}}(I^{\prime})$.

The next principle ensures that one cannot decrease the strength of the MAPs
of a TMLN by adding new and consistent information. The temporal consistency
$\mathtt{Con}:{\mathcal{P}}(\mathtt{TS}$-$\mathtt{FOL})\rightarrow\\{\top,\bot\\}$
denotes a relation of consistence for a set of temporal formulae.

######  Principle 2 (Consistency Monotony)

Let a relation of consistence $\mathtt{Con}$, ${\mathbf{M}}\in\mathtt{TMLN}$
and ${\mathbf{M}}^{\prime}={\mathbf{M}}\cup\\{(\phi,w)\\}$ where $(\phi,w)$ is
a weighted temporal formula such that:

–
$\scalebox{1.2}{$\tau$}(\mathtt{TF}({\mathbf{M}}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi\\})$,
and

– $\forall I\in\mathtt{map}({\mathbf{M}},{\mathcal{S}})$,
$\mathtt{Con}(\\{\phi\\}\cup\mathtt{TF}(I))$ is true and
$I\subset\mathtt{MI}(\\{(\phi,w)\\}\cup I)$.
A semantics ${\mathcal{S}}\in\mathtt{Sem}$ satisfies consistency monotony iff:
$\forall I\in\mathtt{map}({\mathbf{M}},{\mathcal{S}})$ and $\forall
I^{\prime}\in\mathtt{map}({\mathbf{M}}^{\prime},{\mathcal{S}})$,
${\mathcal{S}}(I)\leq{\mathcal{S}}(I^{\prime})$.

The last principle states that if we add a new temporal fact to a TMLN such
that it is consistent with each instantiation, then the fact will be present
in each new instantiation.

######  Principle 3 (Invariant Consistent Facts)

Let a relation of consistence $\mathtt{Con}$, ${\mathbf{M}}\in\mathtt{TMLN}$
and ${\mathbf{M}}^{\prime}={\mathbf{M}}\cup\\{(\phi,w)\\}$ where $(\phi,w)$ is
a TMLN fact such that:

–
$\scalebox{1.2}{$\tau$}(\mathtt{TF}({\mathbf{M}}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi\\})$,
and

– $\forall I\in\mathtt{map}({\mathbf{M}},{\mathcal{S}})$,
$\mathtt{Con}(\\{\phi\\}\cup\mathtt{TF}(I))$ is true.
A semantics ${\mathcal{S}}\in\mathtt{Sem}$ satisfies invariant consistent
facts iff, $\forall I\in\mathtt{map}({\mathbf{M}},{\mathcal{S}})$,
$I\cup\\{(\phi,w)\\}\in\mathtt{map}({\mathbf{M}}^{\prime},{\mathcal{S}})$.

###  4.3 Temporal Consistency and Inconsistency

We study here new temporal consistency interactions required to define our
Temporal MAP inference. Temporal Consistency relations need to be refined
according to the temporal validity of the predicates.For a predicate and its
negation, no clear definition exists to express the temporal consistencies
based on their time intervals. We propose a temporal consistency with a
general case (partial) and a special case (total).

To establish these different temporal consistency relations, we introduce a
function TI to create pre-orders between the temporal constants in the domain
$Time$ of a $\mathtt{TS}$-$\mathtt{FOL}$ and which extracts the interval of
time points from two constants.

######  Definition 9 (Temporal (in)consistency)

Let a set of formulae $\Phi\subseteq\mathtt{TS}$-$\mathtt{FOL}$.

Temporal consistency:

– $\Phi$ has a partial temporal consistency denoted by $\mathtt{pCon}(\Phi)$
iff: $\forall\phi,\psi\in{\mathtt{Cn}}(\Phi)\text{ s.t. }$

$~{}~{}~{}\phi=P(x_{1},$…$,x_{k},t_{1},t_{1}^{\prime})\text{ and }\psi=\neg
P(x_{1},$…$,x_{k},t_{2},t_{2}^{\prime})\text{,
}(\mathtt{TI}(t_{1},t_{1}^{\prime})\setminus\mathtt{TI}(t_{2},t_{2}^{\prime})$

$~{}~{}\neq\emptyset)\wedge(\mathtt{TI}(t_{2},t_{2}^{\prime})\setminus\mathtt{TI}(t_{1},t_{1}^{\prime})\neq\emptyset).$

Otherwise $\neg\mathtt{pCon}(\Phi)$ is true.

– $\Phi$ has a total temporal consistency denoted by $\mathtt{tCon}(\Phi)$
iff: $\forall\phi,\psi\in{\mathtt{Cn}}(\Phi)\text{ s.t. }\phi=$

$~{}~{}~{}P(x_{1},$…$,x_{k},t_{1},t_{1}^{\prime})\text{ and }\psi=\neg
P(x_{1},$…$,x_{k},t_{2},t_{2}^{\prime})\text{,
}(\mathtt{TI}(t_{1},t_{1}^{\prime})\cap\mathtt{TI}(t_{2},t_{2}^{\prime})$=$\emptyset).$

Otherwise $\neg\mathtt{tCon}(\Phi)$ is true.

Temporal inconsistency:

– $\Phi$ has a partial temporal inconsistency denoted by $\mathtt{pInc}(\Phi)$
iff: $\exists\phi,\psi\in{\mathtt{Cn}}(\Phi)\text{ s.t.}$

$~{}~{}~{}\phi$=$P(x_{1},$…$,x_{k},t_{1},t_{1}^{\prime})\text{, }\psi$=$\neg
P(x_{1},$…$,x_{k},t_{2},t_{2}^{\prime})\text{ and
}{\mathtt{TI}(t_{1},t_{1}^{\prime})\cap\mathtt{TI}(t_{2},t_{2}^{\prime})\neq\emptyset.}$

Otherwise $\neg\mathtt{pInc}(\Phi)$ is true.

– $\Phi$ has a total temporal inconsistency denoted by $\mathtt{tInc}(\Phi)$
iff: $\exists\phi,\psi\in{\mathtt{Cn}}(\Phi)\text{ s.t. }$

$~{}~{}~{}\phi=P(x_{1},$…$,x_{k},t_{1},t_{1}^{\prime}),\psi=\neg
P(x_{1},$…$,x_{k},t_{2},t_{2}^{\prime})\text{ and
}(\mathtt{TI}(t_{1},t_{1}^{\prime})=\mathtt{TI}(t_{2},t_{2}^{\prime}).$

Otherwise $\neg\mathtt{tInc}(\Phi)$ is true.

We now examine the interaction properties between
$\mathtt{pCon},\mathtt{tCon},\mathtt{pInc}$ and $\mathtt{tInc}$, such as
complementarity, subsumption and inclusion 111Proofs are available on
https://tinyurl.com/PRICAI22..

######  Definition 10 (Complementarity & Subsumption)

$\forall\Phi\subseteq\mathtt{TS}$-$\mathtt{FOL},\forall\text{ relation
}r_{1},r_{2}\text{ if:}$

– $r_{1}(\Phi)\leftrightarrow\neg r_{2}(\Phi)$ then $r_{1}$ and $r_{2}$ are
complementary.

– $r_{1}(\Phi)\rightarrow r_{2}(\Phi)$ then $r_{1}$ subsume $r_{2}$.

The next two propositions show that firstly $\mathtt{tCon}$ and
$\mathtt{pInc}$ are complementary; secondly different subsumption relations
exist between the temporal consistencies.

###### Proposition 1

(Complementarity: temporal consistencies) For any
$\Phi\subseteq\mathtt{TS}$-$\mathtt{FOL}$:
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\neg\mathtt{tCon}(\Phi)\leftrightarrow\mathtt{pInc}(\Phi)~{}\text{and}~{}\mathtt{tCon}(\Phi)\leftrightarrow\neg\mathtt{pInc}(\Phi)$.

###### Proposition 2

(Subsumption: temporal consisencies) For any
$\Phi\subseteq\mathtt{TS}$-$\mathtt{FOL}$:
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\mathtt{pCon}(\Phi)\rightarrow\neg\mathtt{tInc}(\Phi),~{}~{}\mathtt{tInc}(\Phi)\rightarrow\neg\mathtt{pCon}(\Phi),$
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\neg\mathtt{pCon}(\Phi)\rightarrow\mathtt{pInc}(\Phi),\text{
and}~{}~{}\neg\mathtt{pInc}(\Phi)\rightarrow\mathtt{pCon}(\Phi).$

In the following, for temporal consistency and inconsistency relations, we
denote by $\\{r\\}=\\{\Phi\subseteq$ $\mathtt{TS}$-$\mathtt{FOL}\mid
r(\Phi)\\}$ their set of sets of formulae respecting their condition, where
$r\in\\{\mathtt{pCon},\mathtt{tCon},\mathtt{pInc},\mathtt{tInc},\neg\mathtt{pCon},\neg\mathtt{tCon},\neg\mathtt{pInc},\neg\mathtt{tInc}\\}$.

######  Definition 11 (Inclusion)

Let two relations of temporal consistency
$r_{1},r_{2}\in\\{\mathtt{pCon},\newline \mathtt{tCon},\mathtt{pInc},$
$\mathtt{tInc},\neg\mathtt{pCon},\neg\mathtt{tCon},\neg\mathtt{pInc},\neg\mathtt{tInc}\\}$,
$r_{1}$ is considered included in $r_{2}$ if:
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\{r_{1}\\}\subseteq\\{r_{2}\\}\text{
iff }\forall\Phi\subseteq\mathtt{TS}$-$\mathtt{FOL},r_{1}(\Phi)\rightarrow
r_{2}(\Phi)$.

Some inclusions of temporal consistency relations may be defined between the
sets of sets of formulae respecting them.

###### Proposition 3

(Inclusion: temporal consistencies)
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\{\mathtt{tCon}\\}=\\{\neg\mathtt{pInc}\\}\subseteq\\{\mathtt{pCon}\\}\subseteq\\{\neg\mathtt{tInc}\\}$
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\{\mathtt{tInc}\\}\subseteq\\{\neg\mathtt{pCon}\\}\subseteq\\{\mathtt{pInc}\\}=\\{\neg\mathtt{tCon}\\}$

Links between different relations of temporal consistency are illustrated on
Figure 1.

Figure 1: Links between Consistency and Inconsistency

###  4.4 Temporal Parametric Semantics

To avoid defining several different semantics, we decompose the construction
of semantics and identify three steps. Then, we propose the definition of
Temporal Parametric Semantics, relying on the combination of three functions:
i) a validation function $\Delta$ of instantiations integrating various
consistency relations, ii) a selecting function  $\sigma$ able to modify the
weight of the formulae of an instantiation and iii) an aggregate function
$\Theta$ returning the final strength.

######  Definition 12 (Temporal Parametric Semantics)

A _temporal parametric semantics_ is a tuple
$\mathtt{TPS}=\langle\Delta,\scalebox{1.5}{$\sigma$},\Theta\rangle\in\mathtt{Sem}$,
s.t.:

– $\Delta:\mathtt{TMLN}^{*}\rightarrow\\{0,1\\}$,

–
$\scalebox{1.5}{$\sigma$}:\mathtt{TMLN}^{*}\rightarrow\bigcup^{+\infty}_{k=0}[0,1]^{k}$,

– $\Theta:\bigcup^{+\infty}_{k=0}[0,1]^{k}\rightarrow[0,+\infty[$,

For any ${\mathbf{M}}\in\mathtt{TMLN}$, $I\subseteq\mathtt{MI}({\mathbf{M}})$,
the strength of a temporal parametric semantics
$\mathtt{TPS}=\langle\Delta,\scalebox{1.5}{$\sigma$},\Theta\rangle$ is
computed by:
$\mathtt{TPS}(I)=\Delta(I)\cdot\Theta\Big{(}\scalebox{1.5}{$\sigma$}(I)\Big{)}.$

We propose below key properties that must be satisfied by each of the three
functions $\Delta,\scalebox{1.5}{$\sigma$},\Theta$ of a TPS. Those properties
constrain the range of functions to be considered, and discard those
exhibiting undesired behaviours.

###### Definition 13

A temporal parametric semantics
$\mathtt{TPS}=\langle\Delta,\scalebox{1.5}{$\sigma$},\Theta\rangle$ is _well-
behaved_ according to a temporal consistency relation $\mathtt{Con}$ iff the
following conditions hold:

  1. $\Delta$-

(a)

$\Delta(I)=1$ if $\mathtt{Con}(\mathtt{TF}(I))$ is true (i.e., $I$ is
temporally consistent w.r.t. $\mathtt{Con}$).

  2. $\Theta$-

(a)

$\Theta()=0$.

(b)

$\Theta(w)=w$.

(c)

$\Theta$ is symmetric.

(d)

$\Theta(w_{1},$…$,w_{k})=\Theta(w_{1},$…$,w_{k},0)$.

(e)

$\Theta(w_{1},$…$,w_{k},y)\leq\Theta(w_{1},$…$,w_{k},z)$ if $y\leq z$.

  3. $\sigma$ -

(a)

$\scalebox{1.5}{$\sigma$}()=()$.

(b)

$\scalebox{1.5}{$\sigma$}(\\{(\phi_{1},w_{1}),$…$,(\phi_{k},w_{k})\\})=(w^{\prime}_{1},$…$,w^{\prime}_{n})$
such that if $k\geq 1$ then $n\geq 1$.

(c)

$\scalebox{1.5}{$\sigma$}(\\{(\phi_{1},w_{1}),$…$,(\phi_{k},w_{k}),(\phi_{k+1},0)\\})=(\scalebox{1.5}{$\sigma$}(\\{(\phi_{1},w_{1}),$…$,(\phi_{k},w_{k})\\}),0)$,
if
$\scalebox{1.2}{$\tau$}(\mathtt{TF}(\\{\phi_{1},$…$,\phi_{k}\\}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi\\})$.

(d)

$\scalebox{1.5}{$\sigma$}(\\{(\phi_{1},w_{1}),$…$,(\phi_{k},w_{k})\\})\subset\scalebox{1.5}{$\sigma$}(\\{(\phi_{1},w_{1}),$…$,(\phi_{k},w_{k}),(\phi_{k+1},w_{k+1})\\})$
if $\phi_{k+1}$ is a ground temporal formula,
$\scalebox{1.2}{$\tau$}(\mathtt{TF}(\\{\phi_{1},$…$,\phi_{k}\\}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi_{k+1}\\})$
and
$\mathtt{Con}(\mathtt{TF}(\\{(\phi_{1},w_{1}),$…$,(\phi_{k},w_{k}),(\phi_{k+1},w_{k+1})\\}))$.

(e)

$\Theta\Big{(}\scalebox{1.5}{$\sigma$}(\\{(\phi_{1},w_{1}),$…$,(\phi_{k},w_{k})\\})\Big{)}\leq\Theta\Big{(}\scalebox{1.5}{$\sigma$}(\\{(\phi_{1},w_{1}),$…$,(\phi_{k},w_{k}),$
$(\phi_{k+1},w_{k+1})\\})\Big{)}$ if
$\scalebox{1.2}{$\tau$}(\mathtt{TF}(\\{\phi_{1},$…$,\phi_{k}\\}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi_{k+1}\\})$
and
$\mathtt{Con}(\mathtt{TF}(\\{(\phi_{1},w_{1}),$…$,(\phi_{k},w_{k}),(\phi_{k+1},w_{k+1})\\}))$.

We also say that $\Delta$ is well-behaved according to $\mathtt{Con}$, and
$\Theta,\scalebox{1.5}{$\sigma$}$ are well-behaved.

###### Theorem 4.1

Any temporal parametric semantics well-behaved w.r.t a temporal consistency
relation $\mathtt{Con}$ satisfies the principles from Section 4.2: Temporal
Neutrality, Consistency Monotony and Invariant Consistent Facts (the last two
according to $\mathtt{Con}$).

Once temporal consistency relations are defined, we may enhance semantics for
MAP inference with temporal validation functions. One TMLN instantiation can
be valid or not according to different criteria (i.e., accept an
instantiation).

######  Definition 14 (Temporal Consistency Validation Function)

Let ${\mathbf{M}}\in\mathtt{TMLN}$, an instantiation
$I\subseteq\mathtt{MI}({\mathbf{M}})$ and
$x\in\\{\mathtt{pCon},\mathtt{tCon},\mathtt{pInc},\mathtt{tInc}\\}$. We define
$\Delta_{x}:\mathtt{TMLN^{*}}\rightarrow\\{0,1\\}$, a temporal consistency
validation function according to $x$, such that:

$\begin{array}[]{l}\Delta_{\mathtt{pCon}}(I)=\left\\{\begin{array}[]{ll}1&\text{
if $\mathtt{pCon}(\mathtt{TF}(I))$ }\\\ 0&\text{ if
$\neg\mathtt{pCon}(\mathtt{TF}(I))$}\end{array}\right.\end{array}$
$\begin{array}[]{l}\Delta_{\mathtt{tCon}}(I)=\left\\{\begin{array}[]{ll}1&\text{
if $\mathtt{tCon}(\mathtt{TF}(I))$ }\\\ 0&\text{ if
$\neg\mathtt{tCon}(\mathtt{TF}(I))$}\end{array}\right.\end{array}$
---
$\begin{array}[]{l}\Delta_{\mathtt{pInc}}(I)=\left\\{\begin{array}[]{ll}0&\text{
if $\mathtt{pInc}(\mathtt{TF}(I))$ }\\\ 1&\text{ if
$\neg\mathtt{pInc}(\mathtt{TF}(I))$}\end{array}\right.\end{array}$
$\begin{array}[]{l}\Delta_{\mathtt{tInc}}(I)=\left\\{\begin{array}[]{ll}0&\text{
if $\mathtt{tInc}(\mathtt{TF}(I))$ }\\\ 1&\text{ if
$\neg\mathtt{tInc}(\mathtt{TF}(I))$}\end{array}\right.\end{array}$

###### Corollary 1

For any $I\subseteq\mathtt{TMLN}^{*}$,
$\Delta_{\mathtt{tCon}}(I)=\Delta_{\mathtt{pInc}}(I)$.

###### Corollary 2

Let $x\in\\{\mathtt{pCon},\mathtt{tCon},\mathtt{pInc},\mathtt{tInc}\\}$, each
$\Delta_{x}$ is well-behaved.

We show next that we can order the value of the $\Delta_{x}$ for any
instantiation.

###### Proposition 4

Let ${\mathbf{M}}\in\mathtt{TMLN}$ and $\Delta_{x}$ a temporal consistency
validation function such that
$x\in\\{\mathtt{pCon},\mathtt{tCon},\mathtt{pInc},\mathtt{tInc}\\}$. For any
instantiation $I\subseteq\mathtt{MI}({\mathbf{M}})$:
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\Delta_{\mathtt{tCon}}(I)=\Delta_{\mathtt{pInc}}(I)\leq\Delta_{\mathtt{pCon}}(I)\leq\Delta_{\mathtt{tInc}}(I)$

Theorem 4.2 shows that the strength of the temporal MAP inferences with
$\sigma$ and $\Theta$ on any TMLN is ranked according to the temporal
consistency validation functions $\Delta_{x}$.

###### Theorem 4.2

Let ${\mathbf{M}}\in\mathtt{TMLN}$, for any  $\sigma$ and $\Theta$, we denote
by:

–
$\mathtt{TPS}_{\mathtt{tCon}}=\langle\Delta_{\mathtt{tCon}},\scalebox{1.5}{$\sigma$},\Theta\rangle$,
$\mathtt{TPS}_{\mathtt{pInc}}=\langle\Delta_{\mathtt{pInc}},\scalebox{1.5}{$\sigma$},\Theta\rangle$,

–
$\mathtt{TPS}_{\mathtt{pCon}}=\langle\Delta_{\mathtt{pCon}},\scalebox{1.5}{$\sigma$},\Theta\rangle$,
$\mathtt{TPS}_{\mathtt{tInc}}=\langle\Delta_{\mathtt{tInc}},\scalebox{1.5}{$\sigma$},\Theta\rangle$.
Hence: $\forall
I_{\mathtt{tCon}}\in\mathtt{map}({\mathbf{M}},\mathtt{TPS}_{\mathtt{tCon}})$,
$\forall
I_{\mathtt{pInc}}\in\mathtt{map}({\mathbf{M}},\mathtt{TPS}_{\mathtt{pInc}})$,
$\forall
I_{\mathtt{pCon}}\in\linebreak\mathtt{map}({\mathbf{M}},\mathtt{TPS}_{\mathtt{pCon}})$,
$\forall
I_{\mathtt{tInc}}\in\mathtt{map}({\mathbf{M}},\mathtt{TPS}_{\mathtt{tInc}})$,

$~{}~{}~{}~{}~{}~{}~{}~{}~{}\mathtt{TPS}_{\mathtt{tCon}}(I_{\mathtt{tCon}})=\mathtt{TPS}_{\mathtt{pInc}}(I_{\mathtt{pInc}})\leq\mathtt{TPS}_{\mathtt{pCon}}(I_{\mathtt{pCon}})\leq\mathtt{TPS}_{\mathtt{tInc}}(I_{\mathtt{tInc}}).$

We study different instances of the aggregate function, using different sums.
This type of parameters will determine the strength of an instantiation, in
various ways.

######  Definition 15 (Aggregate Functions)

Let $\\{w_{1},$…$,w_{n}\\}$ such that $n\in[0,+\infty[$ and $\forall
i\in[0,n]$, $w_{i}\in[0,1]$.

– $\Theta_{sum}(w_{1},$…$,w_{n})=\sum^{n}\limits_{i=1}w_{i}$, if $n=0$ then
${\Theta_{sum}()=0.}$

–
$\Theta_{sum,\alpha}(w_{1},$…$,w_{n})=\left(\sum^{n}\limits_{i=1}(w_{i})^{\alpha}\right)^{\frac{1}{\alpha}}$
s.t. $\alpha\geq 1$, if $n=0$ then $\Theta_{sum,\alpha}()=0$.

– $\Theta_{psum}(w_{1},$…$,w_{n})=w_{1}\ominus$…$\ominus w_{n}$, where
$w_{1}\ominus w_{2}=w_{1}+w_{2}-w_{1}\cdot w_{2}$,

if $n=0$ then $\Theta_{psum}()=0$ and if $n=1$ then $\Theta_{psum}(w)=w$.

Those aggregate functions target different kinds of semantics. For instance,
$\Theta_{sum,\alpha}$ emphasises strong weights for inference, while
$\Theta_{psum}$ targets more controversial instantiations (mixed weights).

###### Proposition 5

The three functions $\Theta_{sum}$, $\Theta_{sum,\alpha}$ and $\Theta_{psum}$
are well-behaved.

We propose below a selective function $\scalebox{1.5}{$\sigma$}_{id}$ which
returns all the weights, more complex functions selecting weights with a
threshold ($\scalebox{1.5}{$\sigma$}_{thresh,\alpha}$) and another one,
$\scalebox{1.5}{$\sigma$}_{rule}$, setting the weight of ground rules to 0
when one of their premises is not deductible (i.e., the rule is unusable). The
latter is interesting to say if unground rules (no deductible premises – prem
& imp) must be kept or not in any instantiation.

######  Definition 16 (Selective Functions)

Let ${\mathbf{M}}\in\mathtt{TMLN}$,
$\\{(\phi_{1},w_{1}),$…$,(\phi_{n},w_{n})\\}\subseteq\mathtt{MI}({\mathbf{M}})$:

  * •

$\scalebox{1.5}{$\sigma$}_{id}(\\{(\phi_{1},w_{1}),$…$,(\phi_{n},w_{n})\\})=(w_{1},$…$,w_{n})$

  * •

$\scalebox{1.5}{$\sigma$}_{thresh,\alpha}(\\{(\phi_{1},w_{1}),$…$,(\phi_{n},w_{n})\\})=(\mathtt{max}(w_{1}-\alpha,0),$…$,\mathtt{max}(w_{n}-\alpha,0))$
s.t. $\alpha\in[0,1[$

  * •

    * –

let $\phi=(\psi_{1}\wedge$…$\wedge\psi_{k})\rightarrow\psi_{k+1}$ a rule,
$\mathtt{prem}(\phi)=\\{\psi_{1},$…$,\psi_{k}\\}$.

    * –

$\mathtt{imp}((\phi,w),\\{(\phi_{1},w_{1}),$…$,(\phi_{n},w_{n})\\})=$
$\begin{array}[]{l}\left\\{\begin{array}[]{ll}0&\text{if $\phi$ is a ground
rule}\\\ &\text{s.t. $\exists\psi_{i}\in\mathtt{prem}(\phi)$ }\\\ &\text{s.t.
$\psi_{i}\notin{\mathtt{Cn}}(\\{\phi_{1},$\ldots$,\phi_{n}\\})$ }\\\ w&\text{
otherwise}\end{array}\right.\end{array}$

    * –

$\scalebox{1.5}{$\sigma$}_{rule}(\\{(\phi_{1},w_{1}),$…$,(\phi_{n},w_{n})\\})=\Big{(}\mathtt{imp}((\phi_{1},w_{1}),\\{(\phi_{2},w_{2}),$…,
$(\phi_{n},w_{n})\\}),$…$,\mathtt{imp}((\phi_{n},w_{n}),\\{(\phi_{1},w_{1}),$…$,(\phi_{n-1},w_{n-1})\\})\Big{)}$

###### Proposition 6

The three functions $\scalebox{1.5}{$\sigma$}_{id}$,
$\scalebox{1.5}{$\sigma$}_{thresh,\alpha}$ and
$\scalebox{1.5}{$\sigma$}_{rule}$ are well-behaved.

In [4], the MAP inference uses a semantics working on Herbrand models
(containing temporal formulae, included in $\mathtt{TS}$-$\mathtt{FOL}$) and
built from uncertain ($w<1$) and certain ($w=1$) temporal facts and with a set
of TMLN certain rules. This semantics also determines the temporal
inconsistency by a classical consistency (if there is no formula $\varphi$
such that $\Phi\vdash\varphi$ and $\Phi\vdash\lnot\varphi$) and by summing all
the weights of facts in the instantiation. Therefore, for TMLNs without any
uncertain rule, the MAP inference will return the same instantiations as ours,
using the temporal parametric semantics
$\langle\Delta_{\mathtt{tInc}},\scalebox{1.5}{$\sigma$}_{id},\Theta_{sum}\rangle$.
Our Temporal MAP inference generalises their work.

###  4.5 Example of Reasoning on TMLN

  * Example 2 (Continued). Table 3 illustrates various $\mathtt{TPS}$ leading to different instantiations and possible inferences from Example 2. The last column focuses on the PeasantFamily information which has not been proven yet by Historians. Another interesting analyse is about ”did Nicole Oresme studied at the College of Navarre and when?”.

Temporal Parametric Semantics | Temporal MAP Inferences | Example of Conclusion
---|---|---
$\langle\Delta_{\mathtt{tCon}},\scalebox{1.5}{$\sigma$}_{id},\Theta_{sum}\rangle$ | $\\{\\{F_{6},GR_{11},GR_{12},GR_{2}\\}\\}$ | $(\neg PeasantFamily(NO,t_{min},t_{max}),0.8)$
$\langle\Delta_{\mathtt{pCon}},\scalebox{1.5}{$\sigma$}_{id},\Theta_{sum}\rangle$ | $\\{\\{F_{4},F_{6},GR_{12},GR_{2}\\}\\}$ | $(\neg PeasantFamily(NO,t_{min},t_{max}),0.8)$
$\langle\Delta_{\mathtt{tInc}},\scalebox{1.5}{$\sigma$}_{id},\Theta_{sum}\rangle$ | $\\{\\{F_{4},F_{5},F_{6},GR_{11},GR_{12}\\}\\}$ | $(PeasantFamily(NO,t_{min},t_{max}),0.5)$
$\langle\Delta_{\mathtt{tCon}},\scalebox{1.5}{$\sigma$}_{id},\Theta_{sum,2}\rangle$ | $\\{\\{F_{6},GR_{11},GR_{12},GR_{2}\\}\\}$ | $(\neg PeasantFamily(NO,t_{min},t_{max}),0.8)$
$\langle\Delta_{\mathtt{pCon}},\scalebox{1.5}{$\sigma$}_{id},\Theta_{sum,2}\rangle$ | $\\{\\{F_{4},F_{6},GR_{12},GR_{2}\\}\\}$ | $(\neg PeasantFamily(NO,t_{min},t_{max}),0.8)$
$\langle\Delta_{\mathtt{tInc}},\scalebox{1.5}{$\sigma$}_{id},\Theta_{sum,2}\rangle$ | $\\{\\{F_{4},F_{5},F_{6},GR_{2}\\},$ | $(\neg PeasantFamily(NO,t_{min},t_{max}),0.8)$
|  $\\{F_{5},F_{6},GR_{11},GR_{2}\\}\\}$ |
$\langle\Delta_{\mathtt{tCon}},\scalebox{1.5}{$\sigma$}_{rule},\Theta_{sum}\rangle$ | $\\{\\{F_{4},F_{5},GR_{11},GR_{12}\\}\\}$ | $(PeasantFamily(NO,t_{min},t_{max}),0.5)$
$\langle\Delta_{\mathtt{pCon}},\scalebox{1.5}{$\sigma$}_{rule},\Theta_{sum}\rangle$ | $\\{\\{F_{4},F_{6},GR_{2}\\}\\}$ | $(\neg PeasantFamily(NO,t_{min},t_{max}),0.8)$
$\langle\Delta_{\mathtt{tInc}},\scalebox{1.5}{$\sigma$}_{rule},\Theta_{sum}\rangle$ | $\\{\\{F_{4},F_{5},F_{6},GR_{11},GR_{12}\\}\\}$ | $(PeasantFamily(NO,t_{min},t_{max}),0.5)$
$\langle\Delta_{\mathtt{tCon}},\scalebox{1.5}{$\sigma$}_{rule},\Theta_{sum,2}\rangle$ | $\\{\\{F_{6},GR_{2}\\}\\}$ | $(\neg PeasantFamily(NO,t_{min},t_{max}),0.8)$
$\langle\Delta_{\mathtt{pCon}},\scalebox{1.5}{$\sigma$}_{rule},\Theta_{sum,2}\rangle$ | $\\{\\{F_{4},F_{6},GR_{2}\\}\\}$ | $(\neg PeasantFamily(NO,t_{min},t_{max}),0.8)$
$\langle\Delta_{\mathtt{tInc}},\scalebox{1.5}{$\sigma$}_{rule},\Theta_{sum,2}\rangle$ | $\\{\\{F_{4},F_{5},F_{6},GR_{2}\\}\\}$ | $(\neg PeasantFamily(NO,t_{min},t_{max}),0.8)$
Table 3: TPS example: in each instantiation we omit $F_{1},F_{2},F_{3}$ and
formulae with a 0 weight.

$\Theta_{sum,2}$ keeps highly weighted facts and rules. Instantiations insist
on the conflict between $GR_{11}/GR_{12}$ and $GR_{2}$ (PeasantFamily or not),
keeping those which maximise the strength. More precisely, these ground rules
are temporally inconsistent depending on the set of facts in the
instantiation. Indeed, if ground rules’ premises are not present in the
instantiation, then they have no conflict, as it appears in the $\mathtt{TPS}$
using $\scalebox{1.5}{$\sigma$}_{id}$.

$\scalebox{1.5}{$\sigma$}_{rule}$ gives an interesting vision on the MAP
inference result, since it keeps (i.e., $w>0$) only useful ground rules, i.e.,
rules having deductible premises in the instantiation. Hence,
$\scalebox{1.5}{$\sigma$}_{rule}$ never give importance simultaneously to
$GR_{11}/GR_{12}$ with $GR_{2}$.

Eventually, notice that even if $PeasantFamily(NO,t_{min},t_{max})$ has a
weight of $0.5$ and its negation $0.8$, or even if in this example we have
more inference on the negation, we cannot conclude that $\neg
PeasantFamily(NO,t_{min},t_{max})$ is more likely. For instance,
$\langle\Delta_{\mathtt{tInc}},\scalebox{1.5}{$\sigma$}_{id},\Theta_{sum}\rangle$
corresponding to Chekol’s semantics, advocates that Nicole Oresme was a
Peasant while the one with $\Delta_{\mathtt{pCon}}$ (the partial temporal
consistency) infers the opposite. The parametric choice of our approach would
allow the historian deciding which inference corresponds to their own
reasoning.

##  5 Conclusion

Reasoning on Knowledge Graphs have recently been approached with MLNs, to find
the most probable state of the world. However, they were limited to a strict
temporal inconsistency. We extend UTKGs with a fully-formalized model of TMLN,
capable of combining consistency and inconsistency for facts and rules,
allowing to reason with the MAP inference using new principles and relations
between partial and total aspects of temporal (in-)consistency. Moreover, we
introduce temporal parametric semantics which offer flexibility to tailor
semantics reasoning to one’s needs.

As a perspective, we first wish to extend this work to existential rules in
order to capture more real data (see Section 3.2). Secondly, some
relationships between formulae in a TMLN are not yet exploited and could be
represented with argumentation graphs (e.g., the notion of support [6] or
similarity between pieces of information [1, 2]), to enhance the weight of
inferred knowledge. Thirdly, as we can see in Table 3, each parameter of the
$\mathtt{TPS}$ have an impact on the temporal MAP inferences and its possible
conclusions. It will be useful to investigate some properties to describe the
strategies and specific behaviours of the parametrisation functions. Finally,
implementing our results and confronting them with real data will likely prove
very useful, at least to generate new research hypotheses in historical
science.

## References

  * [1] Amgoud, L., David, V.: Measuring similarity between logical arguments. In: Proceedings of the Sixteenth International Conference on Principles of Knowledge Representation and Reasoning KR. pp. 98–107 (2018)
  * [2] Amgoud, L., David, V.: A General Setting for Gradual Semantics Dealing with Similarity. In: 35th AAAI Conference en Artificial Intelligence (AAAI 2021). AAAI : Association for the Advancement of Artificial Intelligence, AAAI Press, Virtual Conference, United States (Feb 2021), https://hal.archives-ouvertes.fr/hal-03141729
  * [3] Banko, M., Cafarella, M.J., Soderland, S., Broadhead, M., Etzioni, O.: Open information extraction from the web. In: Proceedings of the 20th International Joint Conference on Artifical Intelligence. p. 2670–2676. IJCAI’07, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2007)
  * [4] Chekol, M., Pirrò, G., Schoenfisch, J., Stuckenschmidt, H.: Marrying uncertainty and time in knowledge graphs. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 31 (2017)
  * [5] Chekol, M.W., Huber, J., Meilicke, C., Stuckenschmidt, H.: Markov logic networks with numerical constraints. In: Proceedings of the Twenty-Second European Conference on Artificial Intelligence. p. 1017–1025. ECAI’16, IOS Press, NLD (2016)
  * [6] Cohen, A., Gottifredi, S., García, A.J., Simari, G.R.: A survey of different approaches to support in argumentation systems. The Knowledge Engineering Review 29(5), 513–550 (2014)
  * [7] Dong, X., Gabrilovich, E., Heitz, G., Horn, W., Lao, N., Murphy, K., Strohmann, T., Sun, S., Zhang, W.: Knowledge vault: A web-scale approach to probabilistic knowledge fusion. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. p. 601–610. KDD’14, ACM, New York, NY, USA (2014). https://doi.org/10.1145/2623330.2623623, https://doi.org/10.1145/2623330.2623623
  * [8] Etzioni, O., Banko, M., Soderland, S., Weld, D.S.: Open information extraction from the web. Commun. ACM 51(12), 68–74 (dec 2008). https://doi.org/10.1145/1409360.1409378, https://doi.org/10.1145/1409360.1409378
  * [9] Gallier, J.H.: Logic for computer science: foundations of automatic theorem proving. Courier Dover Publications (2015)
  * [10] Ho, L.T., Arch-int, S., Arch-int, N.: Introducing fuzzy temporal description logic. In: Proceedings of the 3rd International Conference on Industrial and Business Engineering. p. 77–80. ICIBE 2017, Association for Computing Machinery, New York, NY, USA (2017). https://doi.org/10.1145/3133811.3133830, https://doi.org/10.1145/3133811.3133830
  * [11] Jaradeh, M.Y., Singh, K., Stocker, M., Auer, S.: Plumber: A Modular Framework to Create Information Extraction Pipelines, p. 678–679. ACM, New York, NY, USA (2021)
  * [12] Macdonald, E., Barbosa, D.: Neural Relation Extraction on Wikipedia Tables for Augmenting Knowledge Graphs, p. 2133–2136. ACM, New York, NY, USA (2020), https://doi.org/10.1145/3340531.3412164
  * [13] Pujara, J., Miao, H., Getoor, L., Cohen, W.: Knowledge graph identification. In: Alani, H., Kagal, L., Fokoue, A., Groth, P., Biemann, C., Parreira, J.X., Aroyo, L., Noy, N., Welty, C., Janowicz, K. (eds.) The Semantic Web – ISWC 2013\. pp. 542–557. Springer Berlin Heidelberg, Berlin, Heidelberg (2013)
  * [14] Rashid, S.M., Viswanathan, A.K., Gross, I., Kendall, E., McGuinness, D.L.: Leveraging semantics for large-scale knowledge graph evaluation. In: Proceedings of the 2017 ACM on Web Science Conference. p. 437–442. WebSci ’17, ACM, New York, NY, USA (2017). https://doi.org/10.1145/3091478.3162385, https://doi.org/10.1145/3091478.3162385
  * [15] Richardson, M., Domingos, P.: Markov Logic Networks. Machine Learning 62(1), 107–136 (Feb 2006). https://doi.org/10.1007/s10994-006-5833-1, https://doi.org/10.1007/s10994-006-5833-1
  * [16] Riedel, S.: Improving the accuracy and efficiency of map inference for markov logic. arXiv preprint arXiv:1206.3282 (2012)
  * [17] Rincé, R., Kervarc, R., Leray, P.: Complex event processing under uncertainty using markov chains, constraints, and sampling. In: Benzmüller, C., Ricca, F., Parent, X., Roman, D. (eds.) Rules and Reasoning. pp. 147–163. Springer, Cham (2018)
  * [18] Rodionova, A., Bartocci, E., Nickovic, D., Grosu, R.: Temporal logic as filtering. In: Proceedings of the 19th International Conference on Hybrid Systems: Computation and Control. p. 11–20. HSCC ’16, Association for Computing Machinery, New York, NY, USA (2016). https://doi.org/10.1145/2883817.2883839, https://doi.org/10.1145/2883817.2883839
  * [19] Wang, H.: Logic of many-sorted theories. The Journal of Symbolic Logic 17(2), 105–116 (1952)
  * [20] Zalmout, N., Zhang, C., Li, X., Liang, Y., Dong, X.L.: All You Need to Know to Build a Product Knowledge Graph, p. 4090–4091. ACM, New York, NY, USA (2021), https://doi.org/10.1145/3447548.3470825

Supplementary material for
Parameterisation of Reasoning on
Temporal Markov Logic Networks

##  Appendix 0.A Proofs

######  Proof (Proposition 1)

Let $\Phi\subseteq\mathtt{TS}$-$\mathtt{FOL}$ such that $\mathtt{tCon}(\Phi)$,
i.e. from Definition 9:

$\forall\phi,\psi\in{\mathtt{Cn}}(\Phi)\text{ s.t.
}\phi=P(x_{1},\cdots,x_{k},t_{1},t_{1}^{\prime})\text{ and }$ $\psi=\neg
P(x_{1},\cdots,x_{k},t_{2},t_{2}^{\prime})\text{,
}(\mathtt{TI}(t_{1},t_{1}^{\prime})\cap\mathtt{TI}(t_{2},t_{2}^{\prime})=\emptyset)$

then its negation $\neg\mathtt{tCon}(\Phi)$ is equivalent to:

$\neg(\neg\exists\phi,\psi\in{\mathtt{Cn}}(\Phi)\text{ s.t.
}\phi=P(x_{1},\cdots,x_{k},t_{1},t_{1}^{\prime})\text{ and }$ $\psi=\neg
P(x_{1},\cdots,x_{k},t_{2},t_{2}^{\prime})\text{ and
}(\mathtt{TI}(t_{1},t_{1}^{\prime})\cap\mathtt{TI}(t_{2},t_{2}^{\prime})\neq\emptyset))$

Hence $\neg\mathtt{tCon}(\Phi)$ is equivalent to $\mathtt{pInc}(\Phi)$:

$\exists\phi,\psi\in{\mathtt{Cn}}(\Phi)\text{ s.t.
}\phi=P(x_{1},\cdots,x_{k},t_{1},t_{1}^{\prime})\text{ and }$ $\psi=\neg
P(x_{1},\cdots,x_{k},t_{2},t_{2}^{\prime})\text{ and
}(\mathtt{TI}(t_{1},t_{1}^{\prime})\cap\mathtt{TI}(t_{2},t_{2}^{\prime})\neq\emptyset)$

Moreover its negation, $\neg\mathtt{pInc}(\Phi)$ is equivalent to:

$\neg(\neg\forall\phi,\psi\in{\mathtt{Cn}}(\Phi)\text{ s.t.
}\phi=P(x_{1},\cdots,x_{k},t_{1},t_{1}^{\prime})\text{ and }$ $\psi=\neg
P(x_{1},\cdots,x_{k},t_{2},t_{2}^{\prime})\text{,
}(\mathtt{TI}(t_{1},t_{1}^{\prime})\cap\mathtt{TI}(t_{2},t_{2}^{\prime})=\emptyset))$

Therefore $\neg\mathtt{pInc}(\Phi)$ is equivalent to $\mathtt{tCon}(\Phi)$.

######  Proof (Proposition 2)

Let $\Phi\subseteq\mathtt{TS}$-$\mathtt{FOL}$, from Definition 9:

  1. 1.

$\mathtt{pCon}(\Phi)\rightarrow\neg\mathtt{tInc}(\Phi)$:

     * •

$\neg\mathtt{tInc}(\Phi)$ iff,

$\neg\exists\phi,\psi\in{\mathtt{Cn}}(\Phi)\text{ s.t.
}\phi=P(x_{1},\cdots,x_{k},t_{1},t_{1}^{\prime}),$ $\psi=\neg
P(x_{1},\cdots,x_{k},t_{2},t_{2}^{\prime})\text{ and
}(\mathtt{TI}(t_{1},t_{1}^{\prime})=\mathtt{TI}(t_{2},t_{2}^{\prime}))$

     * •

$\mathtt{pCon}(\Phi)$ iff

$\forall\phi,\psi\in{\mathtt{Cn}}(\Phi)\text{ s.t.
}\phi=P(x_{1},\cdots,x_{k},t_{1},t_{1}^{\prime})\text{ and }$ $\psi=\neg
P(x_{1},\cdots,x_{k},t_{2},t_{2}^{\prime})\text{,
}(\mathtt{TI}(t_{1},t_{1}^{\prime})\setminus\mathtt{TI}(t_{2},t_{2}^{\prime})\neq\emptyset)\wedge(\mathtt{TI}(t_{2},t_{2}^{\prime})\setminus\mathtt{TI}(t_{1},t_{1}^{\prime})\neq\emptyset)$

which is equivalent to:

$\neg\exists\phi,\psi\in{\mathtt{Cn}}(\Phi)\text{ s.t.
}\phi=P(x_{1},\cdots,x_{k},t_{1},t_{1}^{\prime})\text{ and }$ $\psi=\neg
P(x_{1},\cdots,x_{k},t_{2},t_{2}^{\prime})\text{ and }$
$(\mathtt{TI}(t_{1},t_{1}^{\prime})\setminus\mathtt{TI}(t_{2},t_{2}^{\prime})=\emptyset)\vee(\mathtt{TI}(t_{2},t_{2}^{\prime})\setminus\mathtt{TI}(t_{1},t_{1}^{\prime})=\emptyset)$

     * •

If there not exists
$\mathtt{TI}(t_{1},t_{1}^{\prime})\setminus\mathtt{TI}(t_{2},t_{2}^{\prime})=\emptyset\text{
or
}\mathtt{TI}(t_{2},t_{2}^{\prime})\setminus\mathtt{TI}(t_{1},t_{1}^{\prime})=\emptyset$
then there not exists
$\mathtt{TI}(t_{1},t_{1}^{\prime})\setminus\mathtt{TI}(t_{2},t_{2}^{\prime})=\emptyset\text{
and
}\mathtt{TI}(t_{2},t_{2}^{\prime})\setminus\mathtt{TI}(t_{1},t_{1}^{\prime})=\emptyset$
(i.e. $\mathtt{TI}(t_{1},t_{1}^{\prime})=\mathtt{TI}(t_{2},t_{2}^{\prime})$),
therefore $\mathtt{pCon}(\Phi)\rightarrow\neg\mathtt{tInc}(\Phi)$.

  2. 2.

$\mathtt{tInc}(\Phi)\rightarrow\neg\mathtt{pCon}(\Phi)$:

     * •

$\neg\mathtt{pCon}(\Phi)$ iff

$\neg(\neg\exists\phi,\psi\in{\mathtt{Cn}}(\Phi)\text{ s.t.
}\phi=P(x_{1},\cdots,x_{k},t_{1},t_{1}^{\prime})\text{ and }$ $\psi=\neg
P(x_{1},\cdots,x_{k},t_{2},t_{2}^{\prime})\text{ and }$
$(\mathtt{TI}(t_{1},t_{1}^{\prime})\setminus\mathtt{TI}(t_{2},t_{2}^{\prime})=\emptyset)\vee(\mathtt{TI}(t_{2},t_{2}^{\prime})\setminus\mathtt{TI}(t_{1},t_{1}^{\prime})=\emptyset))$

i.e.,

$\exists\phi,\psi\in{\mathtt{Cn}}(\Phi)\text{ s.t.
}\phi=P(x_{1},\cdots,x_{k},t_{1},t_{1}^{\prime})\text{ and }$ $\psi=\neg
P(x_{1},\cdots,x_{k},t_{2},t_{2}^{\prime})\text{ and }$
$(\mathtt{TI}(t_{1},t_{1}^{\prime})\setminus\mathtt{TI}(t_{2},t_{2}^{\prime})=\emptyset)\vee(\mathtt{TI}(t_{2},t_{2}^{\prime})\setminus\mathtt{TI}(t_{1},t_{1}^{\prime})=\emptyset)$

     * •

$\mathtt{tInc}(\Phi)$ iff

$\exists\phi,\psi\in{\mathtt{Cn}}(\Phi)\text{ s.t.
}\phi=P(x_{1},\cdots,x_{k},t_{1},t_{1}^{\prime}),$ $\psi=\neg
P(x_{1},\cdots,x_{k},t_{2},t_{2}^{\prime})\text{ and
}(\mathtt{TI}(t_{1},t_{1}^{\prime})=\mathtt{TI}(t_{2},t_{2}^{\prime}))$

     * •

If there exists
$\mathtt{TI}(t_{1},t_{1}^{\prime})\setminus\mathtt{TI}(t_{2},t_{2}^{\prime})=\emptyset\text{
and
}\mathtt{TI}(t_{2},t_{2}^{\prime})\setminus\mathtt{TI}(t_{1},t_{1}^{\prime})=\emptyset$
($\mathtt{TI}(t_{1},t_{1}^{\prime})=\mathtt{TI}(t_{2},t_{2}^{\prime})$), then
there exists
$\mathtt{TI}(t_{1},t_{1}^{\prime})\setminus\mathtt{TI}(t_{2},t_{2}^{\prime})=\emptyset\text{
or
}\mathtt{TI}(t_{2},t_{2}^{\prime})\setminus\mathtt{TI}(t_{1},t_{1}^{\prime})=\emptyset$,
therefore $\mathtt{tInc}(\Phi)\rightarrow\neg\mathtt{pCon}(\Phi)$.

  3. 3.

$\neg\mathtt{pCon}(\Phi)\rightarrow\mathtt{pInc}(\Phi)$:

     * •

$\mathtt{pInc}(\Phi)$ iff

$\exists\phi,\psi\in{\mathtt{Cn}}(\Phi)\text{ s.t.
}\phi=P(x_{1},\cdots,x_{k},t_{1},t_{1}^{\prime})\text{, }$ $\psi=\neg
P(x_{1},\cdots,x_{k},t_{2},t_{2}^{\prime})\text{ and
}(\mathtt{TI}(t_{1},t_{1}^{\prime})\cap\mathtt{TI}(t_{2},t_{2}^{\prime})\neq\emptyset)$

     * •

If there exists
$\mathtt{TI}(t_{1},t_{1}^{\prime})\setminus\mathtt{TI}(t_{2},t_{2}^{\prime})=\emptyset\text{
or
}\mathtt{TI}(t_{2},t_{2}^{\prime})\setminus\mathtt{TI}(t_{1},t_{1}^{\prime})=\emptyset$
then there exists
$\mathtt{TI}(t_{1},t_{1}^{\prime})\cap\mathtt{TI}(t_{2},t_{2}^{\prime})\neq\emptyset$,
therefore $\neg\mathtt{pCon}(\Phi)\rightarrow\mathtt{pInc}(\Phi)$.

  4. 4.

$\neg\mathtt{pInc}(\Phi)\rightarrow\mathtt{pCon}(\Phi)$:

     * •

$\neg\mathtt{pInc}(\Phi)$ is equivalent to:

$\neg(\neg\forall\phi,\psi\in{\mathtt{Cn}}(\Phi)\text{ s.t.
}\phi=P(x_{1},\cdots,x_{k},t_{1},t_{1}^{\prime})\text{ and }$ $\psi=\neg
P(x_{1},\cdots,x_{k},t_{2},t_{2}^{\prime})\text{,
}(\mathtt{TI}(t_{1},t_{1}^{\prime})\cap\mathtt{TI}(t_{2},t_{2}^{\prime})=\emptyset)$

     * •

Therefore, for any
$\mathtt{TI}(t_{1},t_{1}^{\prime}),\mathtt{TI}(t_{2},t_{2}^{\prime})$, if
$\mathtt{TI}(t_{1},t_{1}^{\prime})\cap\mathtt{TI}(t_{2},t_{2}^{\prime})=\emptyset$
then
$\mathtt{TI}(t_{1},t_{1}^{\prime})\setminus\mathtt{TI}(t_{2},t_{2}^{\prime})\neq\emptyset\text{
and
}\mathtt{TI}(t_{2},t_{2}^{\prime})\setminus\mathtt{TI}(t_{1},t_{1}^{\prime})\neq\emptyset$,
therefore $\neg\mathtt{pInc}(\Phi)\rightarrow\mathtt{pCon}(\Phi)$.

######  Proof (Proposition 3)

From Proposition 1 and 2, we know that for any
$\Phi\subseteq\mathtt{TS}$-$\mathtt{FOL}$:

$\mathtt{tCon}(\Phi)\leftrightarrow\neg\mathtt{pInc}(\Phi)\rightarrow\mathtt{pCon}(\Phi)\rightarrow\neg\mathtt{tInc}(\Phi)$
$\mathtt{tInc}\rightarrow\neg\mathtt{pCon}(\Phi)\rightarrow\mathtt{pInc}(\Phi)\leftrightarrow\neg\mathtt{tCon}(\Phi)$

Therefore from Proposition 11:

$\\{\mathtt{tCon}\\}=\\{\neg\mathtt{pInc}\\}\subseteq\\{\mathtt{pCon}\\}\subseteq\\{\neg\mathtt{tInc}\\}$
$\\{\mathtt{tInc}\\}\subseteq\\{\neg\mathtt{pCon}\\}\subseteq\\{\mathtt{pInc}\\}=\\{\neg\mathtt{tCon}\\}$

######  Proof (Theorem 4.1)

.

  * •

Temporal Neutrality.
Let ${\mathbf{M}}\in\mathtt{TMLN}$,
${\mathbf{M}}^{\prime}={\mathbf{M}}\cup\\{(\phi,w)\\}$ where $(\phi,w)$ is a
weighted temporal formula such that:

    * –

$\scalebox{1.2}{$\tau$}(\mathtt{TF}({\mathbf{M}}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi\\})$

    * –

$w=0$.

Given that $(\phi,w=0)$, any new ground formula in the instantiation of
${\mathbf{M}}^{\prime}$ has also a zero weight:
$\forall(\psi,w)\in\mathtt{MI}({\mathbf{M}}^{\prime})\setminus\mathtt{MI}({\mathbf{M}})$,
$w=0$ (because the instantiation take the minimum weight of the formulae
building the ground formula).

If a temporal parametric semantics
$\mathtt{TPS}=\langle\Delta,\scalebox{1.5}{$\sigma$},\Theta\rangle$ is _well-
behaved_ according to a temporal consistency relation $\mathtt{Con}$, then
from Definition 13:

    * –

condition 2.(c): $\Theta(w_{1},\cdots,w_{k})=\Theta(w_{1},\cdots,w_{k},0)$.

    * –

condition 3.(c):
$\scalebox{1.5}{$\sigma$}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),$
$(\phi_{k+1},0)\\})=(\scalebox{1.5}{$\sigma$}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k})\\}),0)$,
if
$\scalebox{1.2}{$\tau$}(\mathtt{TF}(\\{\phi_{1},\cdots,\phi_{k}\\}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi\\})$.

Therefore, any new ground formula will have no impact in any instantiation,
and so in any MAP inference: $\forall
I\in\mathtt{map}({\mathbf{M}},\mathtt{TPS})$ and $\forall
I^{\prime}\in\mathtt{map}({\mathbf{M}}^{\prime},\mathtt{TPS})$,
$\mathtt{TPS}(I)=\mathtt{TPS}(I^{\prime})$.

  * •

Consistency Monotony.
Let a well-behaved temporal semantics
$\mathtt{TPS}=\langle\Delta,\scalebox{1.5}{$\sigma$},\Theta\rangle$ according
to a temporal consistency relation $\mathtt{Con}$,
${\mathbf{M}}\in\mathtt{TMLN}$,
${\mathbf{M}}^{\prime}={\mathbf{M}}\cup\\{(\phi,w)\\}$ where $(\phi,w)$ is a
weighted temporal formula such that:

    1. 1.

$\scalebox{1.2}{$\tau$}(\mathtt{TF}({\mathbf{M}}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi\\})$,
and

    2. 2.

$\forall I\in\mathtt{map}({\mathbf{M}},\mathtt{TPS})$,
$\mathtt{Con}(\\{\phi\\}\cup\mathtt{TF}(I))$ is true and
$I\subset\mathtt{MI}(\\{(\phi,w)\\}\cup I)$.

From Definition 13:

    * –

condition 1.(a): $\Delta(I)=1$ if $\mathtt{Con}(\mathtt{TF}(I))$ is true.

    * –

condition 3.(e):
$\Theta\Big{(}\scalebox{1.5}{$\sigma$}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k})\\})\Big{)}$
$\leq\Theta\Big{(}\scalebox{1.5}{$\sigma$}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),(\phi_{k+1},w_{k+1})\\})\Big{)}$
if
$\scalebox{1.2}{$\tau$}(\mathtt{TF}(\\{\phi_{1},\cdots,\phi_{k}\\}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi_{k+1}\\})$
and
$\mathtt{Con}(\mathtt{TF}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),(\phi_{k+1},w_{k+1})\\}))$.

Therefore, from item 2 of $(\phi,w)$ we know that any new ground formulae are
consistent with each MAP, and with condition 1.(a), we know that the strength
will not down to 0 from $\Delta$. Given that we have at least one new ground
formula in each MAP (condition 2 of Consistency Monotony
$I\subset\mathtt{MI}(\\{(\phi,w)\\}\cup I)$), with condition 3.(e) we know
that:
$\forall I\in\mathtt{map}({\mathbf{M}},\mathtt{TPS})$ and $\forall
I^{\prime}\in\mathtt{map}({\mathbf{M}}^{\prime},\mathtt{TPS})$,
$\mathtt{TPS}(I)\leq\mathtt{TPS}(I^{\prime})$.

  * •

Invariant Consistent Facts.
Let a well-behaved temporal semantics
$\mathtt{TPS}=\langle\Delta,\scalebox{1.5}{$\sigma$},\Theta\rangle$ according
to a temporal consistency relation $\mathtt{Con}$,
${\mathbf{M}}\in\mathtt{TMLN}$,
${\mathbf{M}}^{\prime}={\mathbf{M}}\cup\\{(\phi,w)\\}$ where $(\phi,w)$ is a
TMLN fact such that:

    * –

$\scalebox{1.2}{$\tau$}(\mathtt{TF}({\mathbf{M}}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi\\})$,
and

    * –

$\forall I\in\mathtt{map}({\mathbf{M}},\mathtt{TPS})$,
$\mathtt{Con}(\\{\phi\\}\cup\mathtt{TF}(I))$ is true.

From Definition 13:

    * –

condition 1.(a): $\Delta(I)=1$ if $\mathtt{Con}(\mathtt{TF}(I))$ is true.

    * –

condition 3.(d):
$\scalebox{1.5}{$\sigma$}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k})\\})$
$\subset\scalebox{1.5}{$\sigma$}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),(\phi_{k+1},w_{k+1})\\})$
if $\phi_{k+1}$ is a ground temporal formula,
$\scalebox{1.2}{$\tau$}(\mathtt{TF}(\\{\phi_{1},\cdots,\phi_{k}\\}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi_{k+1}\\})$
and
$\mathtt{Con}(\mathtt{TF}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),(\phi_{k+1},w_{k+1})\\}))$.

Given that $(\phi,w)$ is a TMLN fact, then $\phi$ is a ground formula.
Moreover, from the definition of Temporal MAP Inference, we know that each MAP
is maximal for set inclusion ($\mathtt{map}({\mathbf{M}},S)=\\{I\mid
I\in\underset{I~{}\subseteq~{}\mathtt{MI}({\mathbf{M}})}{\text{argmax}}~{}S(I)\text{
and }$ $\nexists
I^{\prime}\in\underset{I^{\prime}~{}\subseteq~{}\mathtt{MI}({\mathbf{M}})}{\text{argmax}}~{}S(I^{\prime})\text{
s.t. }\\\ I\subset I^{\prime}\\}$). Therefore the new consistent temporal fact
$(\phi,w)$ will be add to any previous MAP: $\forall
I\in\mathtt{map}({\mathbf{M}},\mathtt{TPS})$,
$I\cup\\{(\phi,w)\\}\in\mathtt{map}({\mathbf{M}}^{\prime},\mathtt{TPS})$.

######  Proof (Proposition 4)

. From Definition 11: Let two relations of temporal consistency
$r_{1},r_{2}\in\\{\mathtt{pCon},\mathtt{tCon},\mathtt{pInc},\mathtt{tInc},\neg\mathtt{pCon},\neg\mathtt{tCon},$
$\neg\mathtt{pInc},\neg\mathtt{tInc}\\}$, $r_{1}$ is considered included in
$r_{2}$ if:

$\\{r_{1}\\}\subseteq\\{r_{2}\\}\text{ iff
}\forall\Phi\subseteq\mathtt{TS}-\mathtt{FOL},r_{1}(\Phi)\rightarrow
r_{2}(\Phi)$

From Proposition 3:

$\\{\mathtt{tCon}\\}=\\{\neg\mathtt{pInc}\\}\subseteq\\{\mathtt{pCon}\\}\subseteq\\{\neg\mathtt{tInc}\\}$
$\\{\mathtt{tInc}\\}\subseteq\\{\neg\mathtt{pCon}\\}\subseteq\\{\mathtt{pInc}\\}=\\{\neg\mathtt{tCon}\\}$

Hence, for any set of formulae $\Phi\subseteq\mathtt{TS}$-$\mathtt{FOL}$:

$(\mathtt{tCon}(\Phi)\leftrightarrow\neg\mathtt{pInc}(\Phi))\rightarrow\neg\mathtt{pInc}(\Phi)\rightarrow\mathtt{pCon}(\Phi)\rightarrow\neg\mathtt{tInc}(\Phi)$

From Definition 14:
Let ${\mathbf{M}}\in\mathtt{TMLN}$, an instantiation
$I\subseteq\mathtt{MI}({\mathbf{M}})$ and
$x\in\\{\mathtt{pCon},\mathtt{tCon},\mathtt{pInc},\mathtt{tInc}\\}$.

$\begin{array}[]{l}\Delta_{\mathtt{pCon}}(I)=\left\\{\begin{array}[]{ll}1&\text{
if $\mathtt{pCon}(\mathtt{TF}(I))$ }\\\ 0&\text{ if
$\neg\mathtt{pCon}(\mathtt{TF}(I))$}\end{array}\right.\end{array}$
$\begin{array}[]{l}\Delta_{\mathtt{tCon}}(I)=\left\\{\begin{array}[]{ll}1&\text{
if $\mathtt{tCon}(\mathtt{TF}(I))$ }\\\ 0&\text{ if
$\neg\mathtt{tCon}(\mathtt{TF}(I))$}\end{array}\right.\end{array}$
---
$\begin{array}[]{l}\Delta_{\mathtt{pInc}}(I)=\left\\{\begin{array}[]{ll}0&\text{
if $\mathtt{pInc}(\mathtt{TF}(I))$ }\\\ 1&\text{ if
$\neg\mathtt{pInc}(\mathtt{TF}(I))$}\end{array}\right.\end{array}$
$\begin{array}[]{l}\Delta_{\mathtt{tInc}}(I)=\left\\{\begin{array}[]{ll}0&\text{
if $\mathtt{tInc}(\mathtt{TF}(I))$ }\\\ 1&\text{ if
$\neg\mathtt{tInc}(\mathtt{TF}(I))$}\end{array}\right.\end{array}$

Therefore using the case equal to 1 and given that
$(\mathtt{tCon}(\Phi)\leftrightarrow\neg\mathtt{pInc}(\Phi))\rightarrow\neg\mathtt{pInc}(\Phi)\rightarrow\mathtt{pCon}(\Phi)\rightarrow\neg\mathtt{tInc}(\Phi)$,
for any instantiation $I\subseteq\mathtt{MI}({\mathbf{M}})$:

$\Delta_{\mathtt{tCon}}(I)=\Delta_{\mathtt{pInc}}(I)\leq\Delta_{\mathtt{pCon}}(I)\leq\Delta_{\mathtt{tInc}}(I)$

######  Proof (Theorem 4.2)

Let $x\in\\{\mathtt{pCon},\mathtt{tCon},\mathtt{pInc},\mathtt{tInc}\\}$,
${\mathbf{M}}\in\mathtt{TMLN}$ and $\forall
I\subseteq\mathtt{MI}({\mathbf{M}})$, we know from Proposition 4 that:

$\Delta_{\mathtt{tCon}}(I)=\Delta_{\mathtt{pInc}}(I)\leq\Delta_{\mathtt{pCon}}(I)\leq\Delta_{\mathtt{tInc}}(I)$

From Definition 12, a temporal parametric semantics is defined as follows:

$\mathtt{TPS}(I)=\Delta(I)\cdot\Theta\Big{(}\scalebox{1.5}{$\sigma$}(I)\Big{)}.$

Consequently, $\Delta(I)$ is a coefficient of the combination of  $\sigma$ and
$\Theta$. Thus, for any $I$,  $\sigma$ and $\Theta$, we may order the results
according to the $\Delta(I)$ coefficient.

Finally, given that the MAP Inference returns the instantiation with the
maximum strength, all strengths of the MAP inferences are equal.

Therefore, if we denote by:

  * •

$\mathtt{TPS}_{\mathtt{tCon}}=\langle\Delta_{\mathtt{tCon}},\scalebox{1.5}{$\sigma$},\Theta\rangle$,
$\mathtt{TPS}_{\mathtt{pInc}}=\langle\Delta_{\mathtt{pInc}},\scalebox{1.5}{$\sigma$},\Theta\rangle$,

  * •

$\mathtt{TPS}_{\mathtt{pCon}}=\langle\Delta_{\mathtt{pCon}},\scalebox{1.5}{$\sigma$},\Theta\rangle$,
$\mathtt{TPS}_{\mathtt{tInc}}=\langle\Delta_{\mathtt{tInc}},\scalebox{1.5}{$\sigma$},\Theta\rangle$.

Hence: $\forall
I_{\mathtt{tCon}}\in\mathtt{map}({\mathbf{M}},\mathtt{TPS}_{\mathtt{tCon}})$,
$\forall
I_{\mathtt{pInc}}\in\mathtt{map}({\mathbf{M}},\mathtt{TPS}_{\mathtt{pInc}})$,
$\forall
I_{\mathtt{pCon}}\in\linebreak\mathtt{map}({\mathbf{M}},\mathtt{TPS}_{\mathtt{pCon}})$,
$\forall
I_{\mathtt{tInc}}\in\mathtt{map}({\mathbf{M}},\mathtt{TPS}_{\mathtt{tInc}})$,

$~{}~{}~{}~{}~{}~{}~{}~{}~{}\mathtt{TPS}_{\mathtt{tCon}}(I_{\mathtt{tCon}})=\mathtt{TPS}_{\mathtt{pInc}}(I_{\mathtt{pInc}})\leq\mathtt{TPS}_{\mathtt{pCon}}(I_{\mathtt{pCon}})\leq\mathtt{TPS}_{\mathtt{tInc}}(I_{\mathtt{tInc}}).$

######  Proof (Proposition 5)

Let $\\{w_{1},\cdots,w_{n}\\}$ such that $n\in[0,+\infty[$ and $\forall
i\in[0,n]$, $w_{i}\in[0,1]$.

  * •

$\Theta_{sum}(w_{1},\cdots,w_{n})=\sum^{n}\limits_{i=1}w_{i}$

(a)

$\Theta_{sum}()=0$: by definition.

(b)

$\Theta_{sum}(w_{1})=w_{1}$: $\sum^{1}\limits_{i=1}w_{i}=w_{1}$.

(c)

$\Theta_{sum}(w_{1},\cdots,w_{k})=\Theta_{sum}(w_{1},\cdots,w_{k},0)$: $0$ is
the identity element of the addition.

(d)

$\Theta_{sum}(w_{1},\cdots,w_{k},y)\leq\Theta_{sum}(w_{1},\cdots,w_{k},z)$ if
$y\leq z$: the addition is monotonic.

(e)

$\Theta_{sum}$ is symmetric: the addition is symmetric.

  * •

$\Theta_{sum,\alpha}(w_{1},\cdots,w_{n})=\left(\sum^{n}\limits_{i=1}(w_{i})^{\alpha}\right)^{\frac{1}{\alpha}}$
s.t. $\alpha\geq 1$

(a)

$\Theta_{sum,\alpha}()=0$: by definition.

(b)

$\Theta_{sum,\alpha}(w_{1})=w_{1}$:
$\left(\sum^{1}\limits_{i=1}(w_{i})^{\alpha}\right)^{\frac{1}{\alpha}}=w_{i}$.

(c)

$\Theta_{sum,\alpha}(w_{1},\cdots,w_{k})=\Theta_{sum,\alpha}(w_{1},\cdots,w_{k},0)$:
0 cannot increase with any power and it is the identity element of the
addition.

(d)

$\Theta_{sum,\alpha}(w_{1},\cdots,w_{k},y)\leq\Theta_{sum,\alpha}(w_{1},\cdots,w_{k},z)$
if $y\leq z$: it is a sum of positive element and the addition is monotonic.

(e)

$\Theta_{sum,\alpha}$ is symmetric: the addition is monotonic.

  * •

$\Theta_{psum}(w_{1},\cdots,w_{n})=w_{1}\ominus\cdots\ominus w_{n}$,
where $w_{1}\ominus w_{2}=w_{1}+w_{2}-w_{1}\cdot w_{2}$

(a)

$\Theta_{psum}()=0$: by definition.

(b)

$\Theta_{psum}(w)=w$: by definition.

(c)

$\Theta_{psum}(w_{1},\cdots,w_{k})=\Theta_{psum}(w_{1},\cdots,w_{k},0)$:
$w\ominus 0=w+0-w\cdot 0=w$.

(d)

$\Theta_{psum}(w_{1},\cdots,w_{k},y)\leq\Theta_{psum}(w_{1},\cdots,w_{k},z)$
if $y\leq z$: we know that any $w_{i}\in[0,1]$. From $w_{1}\ominus
w_{2}=w_{1}+w_{2}-w_{1}\cdot w_{2}$ then the addition of $w_{1}+w_{2}$ is
greater than the subtraction of the product $w_{1}\cdot w_{2}$, i.e.
$w_{1}+w_{2}\geq w_{1}\cdot w_{2}$.

(e)

$\Theta_{psum}$ is symmetric: the addition and the product are symmetric.

The three functions $\Theta_{sum}$, $\Theta_{sum,\alpha}$ and $\Theta_{psum}$
are well-behaved.

######  Proof (Proposition 6)

Let ${\mathbf{M}}\in\mathtt{TMLN}$,
$\\{(\phi_{1},w_{1}),\cdots,(\phi_{n},w_{n})\\}\subseteq\mathtt{MI}({\mathbf{M}})$.

  * •

$\scalebox{1.5}{$\sigma$}_{id}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{n},w_{n})\\})=(w_{1},\cdots,w_{n})$

(a)

$\scalebox{1.5}{$\sigma$}_{id}()=()$: by definition.

(b)

$\scalebox{1.5}{$\sigma$}_{id}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k})\\})$
$=(w^{\prime}_{1},\cdots,w^{\prime}_{n})$ such that if $k\geq 1$ then $n\geq
1$: $\forall k\geq 1$, $n=k$.

(c)

$\scalebox{1.5}{$\sigma$}_{id}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),(\phi_{k+1},0)\\})$
$=(\scalebox{1.5}{$\sigma$}_{id}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k})\\}),0)$,
if
$\scalebox{1.2}{$\tau$}(\mathtt{TF}(\\{\phi_{1},\cdots,\phi_{k}\\}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi\\})$:
the function return the initial weight, then any weight doesn’t change and the
0 is added.

(d)

$\scalebox{1.5}{$\sigma$}_{id}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k})\\})$
$\subset\scalebox{1.5}{$\sigma$}_{id}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),(\phi_{k+1},w_{k+1})\\})$
if $\phi_{k+1}$ is a ground temporal formula,
$\scalebox{1.2}{$\tau$}(\mathtt{TF}(\\{\phi_{1},\cdots,\phi_{k}\\}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi_{k+1}\\})$
and
$\mathtt{Con}(\mathtt{TF}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),(\phi_{k+1},w_{k+1})\\}))$:
same reason as in item (c).

(e)

for any well behaved $\Theta$:
$\Theta\Big{(}\scalebox{1.5}{$\sigma$}_{id}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k})\\})\Big{)}$
$\leq\Theta\Big{(}\scalebox{1.5}{$\sigma$}_{id}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),(\phi_{k+1},w_{k+1})\\})\Big{)}$
if
$\scalebox{1.2}{$\tau$}(\mathtt{TF}(\\{\phi_{1},\cdots,\phi_{k}\\}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi_{k+1}\\})$
and
$\mathtt{Con}(\mathtt{TF}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),(\phi_{k+1},w_{k+1})\\}))$:
same reason as in item (c) and (d).

  * •

$\scalebox{1.5}{$\sigma$}_{thresh,\alpha}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{n},w_{n})\\})=(\mathtt{max}(w_{1}-\alpha,0),\cdots,\mathtt{max}(w_{n}-\alpha,0))$
s.t. $\alpha\in[0,1[$

(a)

$\scalebox{1.5}{$\sigma$}_{thresh,\alpha}()=()$: by definition.

(b)

$\scalebox{1.5}{$\sigma$}_{thresh,\alpha}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k})\\})$
$=(w^{\prime}_{1},\cdots,w^{\prime}_{n})$ such that if $k\geq 1$ then $n\geq
1$: : $\forall k\geq 1$, $n=k$.

(c)

$\scalebox{1.5}{$\sigma$}_{thresh,\alpha}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),(\phi_{k+1},0)\\})$
$=\\\
(\scalebox{1.5}{$\sigma$}_{thresh,\alpha}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k})\\}),0)$,
if
$\scalebox{1.2}{$\tau$}(\mathtt{TF}(\\{\phi_{1},\cdots,\phi_{k}\\}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi\\})$:
every 0 still 0 and doesn’t change the rest of the other weights.

(d)

$\scalebox{1.5}{$\sigma$}_{thresh,\alpha}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k})\\})$
$\subset\scalebox{1.5}{$\sigma$}_{thresh,\alpha}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),(\phi_{k+1},w_{k+1})\\})$
if $\phi_{k+1}$ is a grounded temporal formula,
$\scalebox{1.2}{$\tau$}(\mathtt{TF}(\\{\phi_{1},\cdots,\phi_{k}\\}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi_{k+1}\\})$
and
$\mathtt{Con}(\mathtt{TF}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),(\phi_{k+1},w_{k+1})\\}))$.
Any weight is added.

(e)

for any well behaved $\Theta$:
$\Theta\Big{(}\scalebox{1.5}{$\sigma$}_{thresh,\alpha}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k})\\})\Big{)}$
$\leq\Theta\Big{(}\scalebox{1.5}{$\sigma$}_{thresh,\alpha}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),(\phi_{k+1},w_{k+1})\\})\Big{)}$
if
$\scalebox{1.2}{$\tau$}(\mathtt{TF}(\\{\phi_{1},\cdots,\phi_{k}\\}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi_{k+1}\\})$
and
$\mathtt{Con}(\mathtt{TF}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),(\phi_{k+1},w_{k+1})\\}))$.
Any weight is added and the previous weights are independent to new weight
then the aggregation cannot decrease.

  * •

    * –

let $\phi=(\psi_{1}\wedge\cdots\wedge\psi_{k})\rightarrow\psi_{k+1}$ a rule,
$\mathtt{prem}(\phi)=\\{\psi_{1},\cdots,\psi_{k}\\}$.

    * –

$\mathtt{imp}((\phi,w),\\{(\phi_{1},w_{1}),\cdots,(\phi_{n},w_{n})\\})=$
$\begin{array}[]{l}\left\\{\begin{array}[]{ll}0&\text{ if $\phi$ is a ground
rule s.t. $\exists\psi_{i}\in\mathtt{prem}(\phi)$ }\\\ &\text{s.t.
$\psi_{i}\notin{\mathtt{Cn}}(\\{\phi_{1},\cdots,\phi_{n}\\})$ }\\\ w&\text{
otherwise}\end{array}\right.\end{array}$

    * –

$\scalebox{1.5}{$\sigma$}_{rule}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{n},w_{n})\\})=\Big{(}\mathtt{imp}((\phi_{1},w_{1}),\\{(\phi_{2},w_{2}),\cdots,(\phi_{n},w_{n})\\}),\cdots,$
$\mathtt{imp}((\phi_{n},w_{n}),\\{(\phi_{1},w_{1}),\cdots,(\phi_{n-1},w_{n-1})\\})\Big{)}$

(a)

$\scalebox{1.5}{$\sigma$}_{rule}()=()$: by definition.

(b)

$\scalebox{1.5}{$\sigma$}_{rule}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k})\\})$
$=(w^{\prime}_{1},\cdots,w^{\prime}_{n})$ such that if $k\geq 1$ then $n\geq
1$. Any new weight is either added with its weight or with 0 but it is added
then $\forall k\geq 1$, $n=k$.

(c)

$\scalebox{1.5}{$\sigma$}_{rule}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),(\phi_{k+1},0)\\})$
$=(\scalebox{1.5}{$\sigma$}_{rule}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k})\\}),0)$,
if
$\scalebox{1.2}{$\tau$}(\mathtt{TF}(\\{\phi_{1},\cdots,\phi_{k}\\}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi\\})$.
Add a weighted temporal formula with a weight of 0 will still be 0 in any
case.

(d)

$\scalebox{1.5}{$\sigma$}_{rule}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k})\\})$
$\subset\scalebox{1.5}{$\sigma$}_{rule}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),(\phi_{k+1},w_{k+1})\\})$
if $\phi_{k+1}$ is a ground temporal formula,
$\scalebox{1.2}{$\tau$}(\mathtt{TF}(\\{\phi_{1},\cdots,\phi_{k}\\}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi_{k+1}\\})$
and
$\mathtt{Con}(\mathtt{TF}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),(\phi_{k+1},w_{k+1})\\}))$.
Add any new consistent information doesn’t change the other information then
we have a strict inclusion.

(e)

for any well behaved $\Theta$:
$\Theta\Big{(}\scalebox{1.5}{$\sigma$}_{rule}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k})\\})\Big{)}$
$\leq\Theta\Big{(}\scalebox{1.5}{$\sigma$}_{rule}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),(\phi_{k+1},w_{k+1})\\})\Big{)}$
if
$\scalebox{1.2}{$\tau$}(\mathtt{TF}(\\{\phi_{1},\cdots,\phi_{k}\\}))\not\vdash\scalebox{1.2}{$\tau$}(\\{\phi_{k+1}\\})$
and
$\mathtt{Con}(\mathtt{TF}(\\{(\phi_{1},w_{1}),\cdots,(\phi_{k},w_{k}),(\phi_{k+1},w_{k+1})\\}))$.
Add a new information has a weight belonging to 0 and 1, it cannot decrease
the aggregation.

The three functions $\scalebox{1.5}{$\sigma$}_{id}$,
$\scalebox{1.5}{$\sigma$}_{thresh,\alpha}$ and
$\scalebox{1.5}{$\sigma$}_{rule}$ are well-behaved.