Modeling Information Retrieval by Formal Logic: A Survey Modeling Information Retrieval by Formal Logic: A Survey

Logical IR models proposed in the literature differ in two main aspects: (1) the chosen logic $\mathcal {L}$ and (2) the logical value of the formula $d \rightarrow q$ (or of the formula $q \rightarrow d$, as will be explained later in this section) used to determine whether the document $d$ is relevant to the query $q$ within this logic.

As to the second aspect, the mechanism used to determine the relevance of a document $d$ to a query $q$ depends on the meaning of the formula $d \rightarrow q$. Some possible meanings are [86]:

1. for a given logic $\mathcal {L}$, $d \rightarrow q$ is true for a particular interpretation $\delta$, denoted $\lbrace \delta \rbrace \models d \rightarrow q$;
   
2. $q$ is a logical consequence of $d$ in $\mathcal {L}$, denoted $M(d) \models q$;
   
3. the formula $d \rightarrow q$ is valid (a tautology) in $\mathcal {L}$, denoted $\models d \rightarrow q$;
   
4. $d \rightarrow q$ can be derived from a set of formulas $\Gamma$ in $\mathcal {L}$, denoted $ \Gamma \vdash d \rightarrow q$;
   
5. $q$ can be derived from $d$ in $\mathcal {L}$, denoted $ d \vdash q$;
   
6. $d \rightarrow q$ is a theorem of $\mathcal {L}$, that is, derived from the axioms of $\mathcal {L}$, denoted $\vdash d \rightarrow q$.
   

Even if logical consequence (2), validity (3), derivability (5) and theorem derivation (6) are equivalent in sound and complete logics, these notions may encompass rather different meanings depending on the considered logic $\mathcal {L}$. Any IR model adopts one of the above six meanings, and it formalizes the way to compute the relevance of a document $d$ to a query $q$ accordingly. As will be seen in the rest of the article, the notion of validity is the most widely used in the literature. Note that for (2) and (5), $\rightarrow$ is expressed as a meta symbol that does not belong to the logic. This point will be discussed further.

A second difference between the approaches proposed in the literature is the logic selected to model the IR process. For instance, there are IR models founded on propositional logic, first-order logic, modal logic, logical imaging, description logic, and so forth. A first issue to be addressed when formalizing the process of topical relevance assessment in a selected logic is how to express both query and document representations. Within a logical framework both a document $d$ and a query $q$ are formally represented as expressions (formulae) of the selected logical language. The topical connection between them is modeled by allowing the inference of a query from a document or a document from a query. The two above possibilities to set the inferential process provide, of course, different interpretations of the retrieval process; in the literature, both points of view have been explored. More formally, the retrieval process can be modeled by either $d \vdash _\mathcal {L}q$ or $q \vdash _\mathcal {L}d$. In particular, $d \vdash _\mathcal {L}q$ means that by applying the inference rules of $\mathcal {L}$ to $d$ and the set of axioms of $\mathcal {L}$, we can infer $q$.

Formal logics offer a means to include some domain knowledge in the IR process, which is useful for improving the inferential process that assesses document relevance to a query. This has not been sufficiently explored yet, but it deserves further investigation.

Let us suppose that the domain knowledge $\Gamma$ is expressed by means of the formal language of $\mathcal {L}$ and that one models $d \rightarrow q$ by using derivation. In this case, the retrieval decision could be expressed as $\Gamma \cup \lbrace d\rbrace \vdash _\mathcal {L}q$, which means that by applying the inference rules of $\mathcal {L}$ to $d$, the knowledge $\Gamma$, and the set of axioms of $\mathcal {L}$, we can infer $q$. In the former representation $d \vdash _\mathcal {L}q$, the inference of $q$ is based only on $d$ and $\mathcal {L}$, whereas in the latter $\Gamma \cup \lbrace d\rbrace \vdash _\mathcal {L}q$, the inference is also based on $\Gamma$ (thus offering an extension to the point (5) in Section 1.1). As previously outlined, this allows one to formally express and incorporate in a unique formal system the representation of knowledge related to a particular domain of interest.

Semantic approaches to IR actually rely on ad-hoc domain-dependent knowledge resources such as ontologies, knowledge bases, or thesauri. The formal representation and integration of domain knowledge into the considered logic constitutes an effective way to improve the quality of the retrieval process. Therefore, formal logics are a potentially useful mathematical tool to build more accurate ² IR models.

In addition to the abovementioned advantages in supporting an explicit knowledge representation and integration into a logical language, formal logics also offer rich formal languages to represent the content of both documents and queries (especially for documents)³. With a logical language, we can easily represent a situation in which the content of $d$ is about $t_1$ or $t_2$ and not $t_3$ by means of the logical sentence $d=(t_1 \vee t_2) \wedge (\lnot t_3)$.

To summarize, formal logics are powerful tools for knowledge representation, knowledge integration into the IR process, and to represent the inferential nature of the retrieval decision. The most interesting aspects of using formal logics in IR are as follows.

• Formal logics are powerful tools for simulating and modeling the inferential nature of the (topical) relevance assessment process.
  
• Formal logics are well suited to knowledge representation [7, 9, 10] and then for building IR models being capable of formally integrating domain knowledge into the retrieval process [63, 70].
  
• Formal logics offer a rich logical language to represent the content of documents.
  

In this survey, the main logic-based IR models are presented. In Section 2, we categorize the logical IR models according to their different components: considered logic, document $d$ and query $q$ representations, the retrieval decision, and how uncertainty is modeled and its relation to the implication. These different axes allow a multiple comparison of the different models. Section 2 concludes with a general overview of the main logical models proposed in the literature. After this transversal presentation of the state of the art, we describe several logical IR models based on various logics: propositional logic (Section 3), propositional modal logic (Section 4), and the other logics (Section 5). In Section 6, we present information systems, such as semantic web and knowledge graph, which use logical models to access knowledge or information. We present our conclusions in Section 7.

The IR models that are presented and analyzed in this survey are listed in Table 1 with their associated logic. Propositional logic and propositional modal logic are used in several IR models, whereas other logics—such as description logic, first-order logic, and so on—are associated to very few models.

As well outlined in [29], various calculi for uncertainty modeling exist, including probability theory, possibility theory, and belief functions. It is also possible to differentiate between qualitative and quantitative definitions of uncertainty [42]. In relation to logic, the management of uncertainty has been often modeled by means of weights attached to propositions, thus introducing an extension of the employed formal language. For example, if considering propositional logic, the association of a weight with a proposition is a meta-level association. In fact, the truth of propositions remains binary, while the associated weight can express the more or less strong inability to know if a proposition is true or false.

However, several works that have dealt with this kind of extension of the logic language have introduced several misunderstandings related to the role, the meaning, and the properties of those weights [29]. In addition, multi-valued logics have often been wrongly interpreted as logics of uncertainty, while they are basically constructed as truth-functional calculi, and they are compositional (the degree of truth of a formula can be computed based on the degrees of truth of its constituent subformulas).

Thus, while in multi-valued logics the truth value of a sentence $a \wedge b$, for example, is a function of the truth values of its components $a$ and $b$ (compositionality holds), the uncertainty of $a \wedge b$, denoted $U(a \wedge b)$, cannot be determined by using only the uncertainties of its components, that is, $U(a)$ and $U(b)$ (compositionality does not hold) [41].

Multi-valued logics allow definition of multi-valued propositions (e.g., fuzzy propositions when truth values take values in the interval [0,1]).

The reason to model uncertainty in relation to logic-based approaches to IR has been motivated by the need of models able to provide a ranking mechanism of the documents retrieved in response to a query. However, in a logical framework, this purpose can be achieved in two ways: (a) by incorporating an uncertainty modeling in a logical calculus (i.e., as previously outlined, by defining the function $U$); and (b) by adopting a multi-valued logic, such as fuzzy logic, where the propositions are interpreted as fuzzy propositions and their truth value under a given interpretation is a value in the interval [0,1]. For this reason, two possible axes that could be used to categorize the logical models are if they explicitly model uncertainty or if they rely on multi-valued logics.

In the former case, a degree of belief about the truth or validity of $d \rightarrow q$ must be expressed. In this case, what must be expressed is the certainty that $d \rightarrow q$ is true. In the latter case, any belief or uncertainty is expressed within the logic: for example, in fuzzy logic, each proposition has a truth value expressed as a numeric value in [0,1], which allows the expression of partial truth. This numeric degree does not express any uncertainty: as well outlined in [29], “degrees of uncertainty are clearly a higher level notion, higher than degrees of truth.”

Table 5 shows the different IR models considering either the degree of belief or multi-valued logics.

We presented in Section 2 our fine-grained analysis and categorization of logical models. To offer the readers a self-contained survey, we present in Sections 3, 4, and 5 a synthesis of the most prominent logical IR models and their underlying mathematical logic. However, before detailing logical IR models, Table 6 presents an overview of these models. It indicates for each model its definition of each part of the IR process: term, document, query, matching, and ranking. This table offers a summary of the next sections.

Table 6. Logic-based IR Models

Model	$t$	$d$	$q$	$d \rightarrow q$	$U(d \rightarrow q)$
Propositional Logic $\mathcal {PL}$ –based models
Losada and Barreiro [59]	proposition	sentence	sentence	$d \models q$	Dalal's BR ($\circ _D$)
Picard and Savoy [74]	proposition	fact	sentence	$d \supset q$	cond. prob.
Abdulahhad [1]	proposition	sentence	sentence	$\models d \supset q$	Lattice+prob.
Propositional Modal Logic $\mathcal {PML}$ –based models
Nie [67, 68]	proposition	poss. world	sentence	path $d_0 \dots d_n$	path's cost
Nie [69]	proposition	poss. world	sentence	-	imaging $P_d(q)$
Crestani and van Rijsbergen [23]	poss. world	sentence	sentence	-	imaging $P_d(q)$
Nie et al. [70]	proposition	poss. world	sentence	path $d_0 \dots d_n$	fuzzy dist.
Description Logic $\mathcal {DL}$ –based models
Meghini et al. [63]	-	individual	concept	assertion $d:q$	-
Sebastiani [85]	-	individual	concept	assertion $d:q$	probability
First-Order Logic $\mathcal {FL}$ –based models
Chevallet and Chiaramella [16]	-	conc. graph	conc. graph	proj. $d \le q$	graph op. cost
Probabilistic Datalog–based models
Fuhr [34]	-	ground facts	Bool. expr.	inference rule	probability
Fuzzy Logic $\mathcal {FZL}$ –based models
Pasi [72]	-	fuzzy set	Bool. exp.	$q \supset d$	fuzzy implication
Bosc et al. [12]	-	fuzzy set	Bool. exp.	$q \supset d$	fuzzy implication
Ughetto et al. [91]	-	fuzzy set	Bool. exp.	$q \supset d$	fuzzy implication
Situation Theory$\mathcal {ST}$ –based models
Lalmas and van Rijsbergen [53]	-	situation	infon	$d$ supports $q$	cond. constraint
Default Logic based models
Hunter [46]	proposition	clause	sentence	$d \supset q$	positioning

The next sections present each logical IR model within its logic in the order presented in Table 6. Section 3 describes models based on propositional logic, Section 4 describes those based on propositional modal logic, and Section 5 gathers the models based on all other logics.

$\mathcal {PL}$, or zero-order logic, is defined on a finite set of atomic propositions or alphabet $\Omega =\lbrace a_1,\dots ,a_n\rbrace$ and a finite set of connectives $\Upsilon$. One of standard sets of connectives is $\Upsilon =\lbrace \lnot , \wedge , \vee \rbrace$. Depending on the alphabet $\Omega$ and the connectives $\Upsilon$, a set of well-formed logical sentences $\Sigma$ is defined as follows.

• Any atomic proposition is a well-formed logical sentence: $\forall a \in \Omega , a \in \Sigma$.
  
• The negation of a logical sentence is also a logical sentence: $\forall s \in \Sigma , \lnot s \in \Sigma$.
  
• The conjunction of any two logical sentences is also a logical sentence: $\forall s_1,s_2 \in \Sigma , s_1 \wedge s_2 \in \Sigma$.
  
• The disjunction of any two logical sentences is also a logical sentence: $\forall s_1,s_2 \in \Sigma , s_1 \vee s_2 \in \Sigma$.
  
• $\Sigma$ does not contain any other sentences.
  

Material implication $\supset$ is implicitly included in $\Upsilon$ where, for any two logical sentences $s_1$ and $s_2$, the material implication $s_1 \supset s_2$ is equivalent to $\lnot s_1 \vee s_2$.

In $\mathcal {PL}$, a formal semantics or interpretation is given to a logical sentence $s$ through assigning a truth value ($T$ or $F$) to each atomic proposition in $s$. Each interpretation corresponds to a mapping between all atomic propositions and the set of truth values $\lbrace T,F\rbrace$. The set of atomic propositions $\Omega$ thus corresponds to $2^{|\Omega |}$ possible interpretations because each atomic proposition $a \in \Omega$ is mapped to one of two possible values ($T$ or $F$).

First, we define the set of all possible mappings $\Pi _\Omega$ between the set of atomic propositions $\Omega$ and the truth values $\lbrace T,F\rbrace$, where

Any logical sentence $s \in \Sigma$ can be true or false in a specific interpretation $\delta \in \Delta _\Omega$. If $s$ is true in $\delta$, then it is denoted $\lbrace \delta \rbrace \models s$ and is read as $\delta$ satisfies or models $s$; otherwise, it is denoted $\lbrace \delta \rbrace \not\models s$. The truth value of an arbitrary logical sentence in $\Sigma$ with respect to an interpretation is determined as follows:

• $\forall \delta \in \Delta _\Omega , \forall a \in \Omega , \lbrace \delta \rbrace \models a \mbox{ iff } a \in \delta$.
  
• $\forall \delta \in \Delta _\Omega , \forall s \in \Sigma , \lbrace \delta \rbrace \models \lnot s \mbox{ iff } \lbrace \delta \rbrace \not\models s$.
  
• $\forall \delta \in \Delta _\Omega , \forall s_1,s_2 \in \Sigma , \lbrace \delta \rbrace \models s_1 \wedge s_2 \mbox{ iff } \lbrace \delta \rbrace \models s_1 \mbox{ and } \lbrace \delta \rbrace \models s_2$.
  
• $\forall \delta \in \Delta _\Omega , \forall s_1,s_2 \in \Sigma , \lbrace \delta \rbrace \models s_1 \vee s_2 \mbox{ iff } \lbrace \delta \rbrace \models s_1 \mbox{ or } \lbrace \delta \rbrace \models s_2$.
  

For any logical sentence $s$, the subset $M(s) \subseteq \Delta _\Omega$ that satisfies $s$ is called the set of models of $s$, denoted $M(s) \models s$, where, for any interpretation $\delta \in M(s),$ we have that $\lbrace \delta \rbrace \models s$. That is, if we substitute each atomic proposition in $s$ by its truth value in $\delta ,$ then the truth value of $s$ will be true. The notation $\models s$ means that $s$ is a tautology or , or, in other words, $s$ is true under any interpretation (i.e., $M(s)=\Delta _\Omega$). The notation $\not\models s$ means that $s$ is false under all interpretations or unsatisfiable (i.e., $M(s)=\emptyset$). For example, assume that $\Omega =\lbrace a,b\rbrace$ and assume that the logical sentence is the material implication $a \supset b$. The set of models $M(a \supset b)$ of $a \supset b$ is depicted in Table 8, where $M(a \supset b)=\lbrace \delta _1,\delta _2,\delta _4\rbrace$. The set of models $M(s)$ is the set of models of a set of sentences logically equivalent to $s$. For example, $M(a \supset b)=M(\lnot a \vee b)$ where it is well known that $a \supset b$ and $\lnot a \vee b$ are equivalent. It is also known that, for any two logical sentences $s_1$ and $s_2$, we have that

There are two main assumptions concerning the atomic propositions that do not occur in a sentence:

• Closed-World Assumption (CWA): For a sentence $s$, if an atomic proposition does not occur in $s,$ then it is implicitly false. For example, assume that $\Omega =\lbrace a,b,c\rbrace$; then, under CWA, $M(a \wedge b)=\lbrace \delta _7\rbrace$ (Table 7), where $c$ must be false.
  
• Open-World Assumption (OWA): For a sentence $s$, if an atomic proposition does not occur in $s$, then it can be either true or false. For example, assume that $\Omega =\lbrace a,b,c\rbrace$. Then, under the OWA, $M(a \wedge b)=\lbrace \delta _7,\delta _8\rbrace$ (Table 7), where $c$ can be true or false.
  

$\mathcal {PL}$ is a special kind of formal logic, where it is complete and sound. Completeness and soundness govern the relation between provability $\vdash$ and satisfiability $\models$. Completeness means that if $M(s_1) \models s_2$, then $s_1 \vdash s_2$. Soundness means that if $s_1 \vdash s_2$, then $M(s_1) \models s_2$.

Losada and Barreiro [59] use $\mathcal {PL}$ to build an IR model. Each index term is an atomic proposition that could be either true or false under the interpretation offered by a particular document or query. A document $d$ is a logical sentence formed using the index terms. A query $q$ is also a logical sentence. The retrieval decision is a logical consequence or entailment, where $d$ is relevant to $q$ iff $d \models q$. Since the model is proposed in the $\mathcal {PL}$ framework, $d \models q$ is equivalent to $\models d \supset q$. In the formal semantics of $\mathcal {PL}$, $d \models q$ means that every model of $d$ is also a model of $q$ or, in other words, for every interpretation $\delta$ in which $d$ is true, $q$ is also true.

To estimate the uncertainty of $d \models q$, denoted $U(d \models q)$, Losada and Barreiro use the framework of Belief Revision (BR), which is a technique to formally express the notion of proximity between logical sentences. BR deals with updating an existing knowledge $K$ with a new piece of information $s$, denoted $K \circ s$, where, if there is no contradiction between $K$ and $s$, then the updated knowledge becomes $K \circ s = K \wedge s$; otherwise, BR deals with the minimal change that should be made to $K$ in order to build an updated knowledge $K^{\prime }$ that does not contradict s, $K \circ s = K^{\prime } \wedge s$. This last notion of minimal change is central to IR.

There are several BR techniques that deal with the syntax of the logical language, that is, formula-based approaches [66], and other techniques that deal with the formal semantics of the logic, that is, model-based approaches [73]. Losada and Barreiro use Dalal's BR operator [26], denoted $\circ _D$, which is one of the model-based approaches of BR. According to this operator, giving two interpretations $\delta _i$ and $\delta _j$, the distance between them, denoted $\mathit {dist}(\delta _i,\delta _j)$, is the number of atomic propositions in which the two interpretations differ. For example, let us assume that our alphabet $\Omega$ contains three atomic propositions $\Omega =\lbrace a,b,c\rbrace$. Assume that we have two interpretations: $\delta _i=\lbrace a,b\rbrace$, which means that $a$ and $b$ are true whereas $c$ is implicitly false, $\delta _j=\lbrace a,c\rbrace$, which means that $a$ and $c$ are true whereas $b$ is implicitly false. The distance between $\delta _i$ and $\delta _j$ is

To estimate the uncertainty of the retrieval decision $U(d \models q)$ by using Dalal's BR operator, Losada and Barreiro distinguish between two modes of revision:

• Revising $q$ by $d$, denoted $q \circ _D d$. Here, there are two cases:
  
  • $q$ has several models $M(q)$ whereas $d$ has only a unique model $m_d$ (CWA).
    \[ \mathit {distance}(d,q) = \mathit {Dist}(M(q),m_d) \]
    
    
  • $q$ has several models $M(q)$ and $d$ also has several models $M(d)$ (OWA).
    \[ \mathit {distance}(d,q) = \frac{\sum _{m \in M(d)} \mathit {Dist}(M(q),m)}{|M(d)|} \]
    
    
  Now, the similarity between $d$ and $q$ is
  \[ \mathit {BRsim}(d,q) = 1 - \frac{\mathit {distance}(d,q)}{k}, \]
  where $k$ is the number of atomic propositions appearing in $q$.
  
• Revising $d$ by $q$, denoted $d \circ _D q$.
  \[ \mathit {distance}(q,d) = \frac{\sum _{m \in M(q)} \mathit {Dist}(M(d),m)}{|M(q)|}. \]
  Now, the similarity between $d$ and $q$ is
  \[ \mathit {BRsp}(d,q) = 1 - \frac{\mathit {distance}(q,d)}{l}, \]
  where $l$ is the number of atomic propositions appearing in $d$.
  

According to Losada and Barreiro, the final retrieval score is a linear combination of the two similarities:

Losada and Barreiro propose rewriting the logical sentences in Disjunctive Normal Form (DNF) and, instead of computing the distance between $d$ and $q$ based on interpretations, they compute it based on clauses. A sentence $s$ in DNF is a disjunction of clauses $c_1 \vee \dots \vee c_n$ and each clause $c_i$ is a conjunction of literals $l_1 \wedge \dots l_m$ and each literal $l_j$ is either an atomic proposition $a_j$ or its negation $\lnot a_j$. The distance between two clauses is the number of atomic propositions that are positive in one clause and negative in the other, computed as follows:

To sum up, since atomic propositions correspond to the index terms, the distance measure calculates how many different terms exist between $d$ and $q$. Losada and Barreiro claim that their model is equivalent to the vector space model (VSM) [83] with a more powerful language to represent the content of documents and queries but without the ability to represent term weights.

Probabilistic argumentation systems (PASs) [40] extends propositional logic ($\mathcal {PL}$) by a mechanism that allows expression of uncertainty by using probability theory. The uncertainty is captured by means of special propositions called assumptions. Uncertain rules in PASs are generally defined as follows:

A knowledge base $K$ is a set of uncertain rules of the previous form. It is possible to check whether a knowledge base $K$ supports or discounts a particular hypothesis $h$, where $h$ is any logical sentence. The support of a hypothesis $h$ in a knowledge base $K$, denoted $\mathit {sp}(h,K)$, is the disjunction of the assumptions $a_i$, where for any assumption $a_i$ we have that $(a_i \wedge K) \models h$. The degree of support of a hypothesis $h$ in a knowledge base $K$, denoted $\mathit {dsp}(h,K)$, refers to the degree to which $K$ supports $h$ knowing that $h$ does not contradict $K$. The degree of support $\mathit {dsp}(h,K)$ is the quantitative or numerical expression of the support $\mathit {sp}(h,K)$, and $\mathit {dsp}(h,K)$ is a type of conditional probability.

Picard and Savoy [74] use PAS to build an IR model. According to Picard and Savoy, documents, queries, and the indexing terms are atomic propositions. The content of documents and queries is represented by a set of rules of the following form:

The set of previous rules forms the IR knowledge base $K$. The retrieval decision $d \rightarrow q$ is the material implication $d \supset q$. The uncertainty $U(d \supset q)$ is estimated in two possible ways:

• either symbolically: $U(d \supset q) = \mathit {sp}(q,K \wedge d)$
  
• or numerically: $U(d \supset q) = \mathit {dsp}(q,K \wedge d)$.
  

In both ways, the document $d$ is assumed as a fact or it is observed. The knowledge base $K$ is updated according to this observation to become $K \wedge d$. Actually, the model captures the degree to which the new knowledge base $K \wedge d$ supports the query $q$.

The formalism presented by Picard and Savoy is capable of representing the inter-terms relationships through rules of the form: $b_{ij} \wedge t_i \rightarrow t_j$. However, Picard and Savoy emphasize the ability of their formalism to represent the inter-document relationships, for example, hyperlinks, citations, and the like. They employ rules of the form: $l_{ij} \wedge d_i \rightarrow d_j$ to represent this type of relation, where $d_i$ is related to $d_j$ by a link directed from $d_i$ to $d_j$, and the probability $P(l_{ij})$ reflects the type of relation and its strength. The main disadvantage is that estimating $P(a_{ij})$, $P(b_{ij})$, $P(l_{ij})$ in the previous rules requires the availability of relevance information. The probability $P(a_{ij})$ in the rule $a_{ij} \wedge d_i \rightarrow t_j$ is estimated by using a variant of the classical tf.idf measure. In general, the main difficulty in this study is the probability estimation.

There is a mathematical link between $\mathcal {PL}$ and probability via lattices [20, 47, 48]. There are several ways to express the link between $\mathcal {PL}$ and lattices [3, 48]. The classical way is through the formal semantics of $\mathcal {PL}$. Assume the set of atomic propositions $\Omega$. On the one hand, the following structure $L=(2^{2^\Omega },\cap ,\cup)$ is a distributive lattice, where $2^{2^\Omega }$ is the powerset of the powerset of $\Omega$, $\cap$ is the meet operation, $\cup$ is the join operation, and the partial order relation defined on the lattice $L$ is the set inclusion $\forall x,y \in 2^{2^\Omega }, x \le y \Leftrightarrow x \subseteq y$. On the other hand, each logical sentence $s$ in $\mathcal {PL}$ corresponds to a set of models $M(s)$, where each model $m \in M(s)$ is the set of atomic propositions that must be set to true in this model; hence, $m \in 2^\Omega$ and $M(s) \in 2^{2^\Omega }$. Furthermore, for any two sentences $s_1,s_2$, we have that $\models s_1 \supset s_2$ is equivalent to $M(s_1) \subseteq M(s_2)$, where $s_1 \supset s_2$ is the material implication. Accordingly, the potential link between $\mathcal {PL}$ and lattices can be formed as follows: any logical sentence $s$ corresponds to a node $M(s)$ on the lattice $L$, and the partial order relation defined on $L$ is equivalent to the validity of material implication, where $\models s_1 \supset s_2$ is equivalent to $M(s_1) \le M(s_2)$.

On the other side, the link between uncertainty (probability as a special case) and lattices is defined as follows: partial order relations are binary, that is, either $x$ is smaller than $y$ or not. However, partial order relations can be quantified where, instead of saying that $x$ is smaller than $y$ or not, we estimate the degree to which $x$ includes $y$, denoted $Z(x,y)$:

Accordingly, lattices can form the mathematical link between formal logics and uncertainty. Abdulahhad et al. [3] exploit this fact in order to build their IR model. In their work, the document $d$ is a logical sentence written in DNF⁶. The query $q$ is a logical sentence written in DNF. The retrieval decision $d \rightarrow q$ is the validity of material implication $\models d \supset q$ [2]. Before defining the uncertain implication $U(d \rightarrow q)$, the mathematical link between $\mathcal {PL}$ and lattices is redefined, where instead of sets of elements as nodes, they build a new lattice $L^{\prime }$ with nodes as flat sets of elements. In this new lattice $L^{\prime }$, each clause (not each sentence as in $L$) corresponds to a node and the partial-order relation is equivalent to the validity of material implication between clauses. Accordingly, $d$ corresponds to one or several nodes in $L^{\prime }$, because $d$ is a logical sentence written in DNF, and then it consists of one or several clauses; $q$ also corresponds to one or several nodes in $L^{\prime }$. The retrieval decision corresponds to the partial-order relation of $L^{\prime }$.

The uncertainty $U(d \rightarrow q)$ is estimated by exploiting the mathematical link between lattices and uncertainty (the previously defined $Z$ function). Assume that $d$ and $q$ are clauses, then

This work shows that the vectorial inner product is a possible implementation of $Z$ [1]. According to this observation, several operational variants of their theoretical model are built.

In Section 3.1, we present the formal interpretation and semantics of $\mathcal {PL}$. Kripke's semantics [50], or PW semantics, is another way to give a formal meaning to logical sentences; it is recommended to give a formal semantics to $\mathcal {PML}$. For more detailed information about modal logics, refer to [44].

PW semantics has the structure $\langle W,R \rangle$, where $W$ is a non-empty set of what is conventionally called Possible Worlds, and $R$ is a binary relation $R \subseteq W \times W$, conventionally called accessibility relations. The structure defines Kripke's system, where determines if any sentence $s$ is true in a world $w$ (denoted as ) or if it is not true, denoted as . The semantics of classical $\mathcal {PL}$ connectives (conjunction $\wedge$, disjunction $\vee$, negation $\lnot$) in Kripke's system is defined as follows:

• Negation: iff .
  
• Conjunction: iff and .
  
• Disjunction: iff or .
  

As previously said, $\mathcal {PML}$ defines two special unary operators, Necessarily () and Possibly (). The formal semantics of these operators in Kripke's system is as follows:

• Necessarily: iff for any world $w^{\prime }$ satisfying $(w,w^{\prime }) \in R$, . Conventionally, we could say that $s$ is necessarily true in $w$ iff $s$ will be true in any future moment.
  
• Possibly: iff there exists a world $w^{\prime }$ satisfying $(w,w^{\prime }) \in R$, . Here, also, we could say that $s$ is possibly true in $w$ iff there exists at least one future moment in which $s$ will be true.
  

The notation $(w,w^{\prime }) \in R$ means that the world $w^{\prime }$ is accessible from $w$ through the accessibility relation $R$. The properties of the accessibility relation $R$ or, equivalently, the way of interaction between the added operators () and the classical operators ($\wedge ,\vee ,\lnot$), determines different families of $\mathcal {PML}$, having different expressive powers. Some families of $\mathcal {PML}$ are sound and complete.

Imaging is a process developed in the framework of The Logic of Conditionals. Lewis [55] demonstrated that the probability of conditionals cannot be the standard conditional probability. However, we need a revised probability (via imaging), where the probability of conditionals is the corresponding revised conditional probability [4, 6]. Imaging also enables the evaluation of a conditional sentence $a \rightarrow b$ without explicitly defining the operator $\rightarrow$. Technically, to define imaging, let us first assume that a probability distribution $P$ is defined on the set of possible worlds $W$ as follows:

• The truth of $s$ in a world $w$ is no more binary.
  
  Furthermore, for any logical sentence $s$, the following condition holds: $\sum _{w \in W} w(s) = 1$.
  
• There could be more than one most similar world. Therefore, $w_s$ is no more one distinct world, it is now a set of worlds, where $w_s$ are the worlds the most similar to $w$ where $s$ is true, that is, $\forall w^{\prime } \in w_s, w^{\prime }(s)\gt 0$.
  

After defining a probability distribution on worlds, the probability can also be defined on logical sentences. For any logical sentence $s$,

The probability of a condition $s_1 \rightarrow s_2$ is defined as follows [4, 21, 23]:

Nie [67, 68] uses $\mathcal {PML}$, or Kripke's formal semantics [50], to refine the LUP that is proposed by van Rijsbergen [94]. Nie defines his logic-based IR model within the formal semantics layer. The inference mechanism in Nie's model has no direct correspondence in the formal language of $\mathcal {PML}$.

Nie assumes that a document $d$ is a set of logical sentences or, equivalently, it corresponds to a possible world. A query $q$ is a set of propositions or a logical sentence. Any proposition $a$ is true in $d$ if it appears in $d$. To evaluate $U(d \rightarrow q)$, the model starts from the initial world $d$ (or $d_0$); if $q$ is not satisfied in $d_0$, then, using accessibility relations, the model moves from $d_0$ to $d_1$. If $q$ is still not satisfied in $d_1$, the model moves from $d_1$ to $d_2$, and so on, until the model arrives to $d_n$ that satisfies $q$. Actually, there are many paths from $d_0$ to $d_n$. Therefore, to calculate the certainty of the implication $U(d \rightarrow q)$, the path of the minimal distance is chosen. A general measure to calculate the distance from $d_0$ to $d_n$, denoted $\mathit {dis}(d_0,d_n)$, is defined as a function of the elementary distances $\mathit {dis}(d_i,d_{i+1})$.

In a symmetric approach, instead of considering documents as possible worlds, it is possible to consider queries as possible worlds. In this case, the model must find the path from $q_0$ to $q_n$ that satisfies $d$. In both cases, the accessibility relations between possible worlds could be linguistic relations. For example, the model could move from $q_i$ to $q_{i+1}$ by adding the synonymous terms of the indexing terms of $q_i$ to $q_{i+1}$ (query expansion). Nie reformulated the LUP as follows:

Given any two information sets $x$ and $y$; a measurement of the uncertainty of $y \rightarrow x$ relative to a given knowledge set $K$, is determined by the minimal extent $E$ to which we have to add information to $y$, to establish the truth of $(y+E) \rightarrow x$.

The implication $d \rightarrow q$ is thus equivalent to finding a path from the initial possible world $d$ to another possible world $d_n$ that satisfies $q$, whereas, the uncertainty $U(d \rightarrow q)$ is equivalent to the cost or the total distance of this path. The matching score $\mathit {RSV}(d,q)$ according to Nie is a function $F$ of the two uncertain implications:

In the studies of Nie [67, 68], the distance between worlds or the cost of accessibility relations is informally defined. However, Nie [69] defines two sources of uncertainty in a formal way⁷:

• The truth of a proposition $a$ in a world $w$ is not binary, $w(a) \in [0,1]$. The function $w()$ is recursively defined on any logical sentence, and Nie proved that it is a probability.
  
• The strength of the accessibility relation between two worlds $w$ and $w^{\prime }$ depends on the type of semantic relation for example, synonymy, generalization, and specialization—that causes the transformation of $w$ to $w^{\prime }$, where $\sum _{w^{\prime } \in W} P^w(w^{\prime }) = 1$.
  

Nie [69] uses probability (imaging) to estimate the logical uncertainty $U(d \rightarrow q)$. According to Nie, a document $d$ is a possible world and a query $q$ is a logical sentence. First, the model of Nie makes an imaging on $d$ to transform probabilities from the worlds that have an accessibility relation with $d$, to $d$. To compute the logical uncertainty $U(d \rightarrow q)$, Nie uses Equation (1), where

Unlike Nie, who represents a document $d$ as a possible world, a query $q$ as a logical sentence. $d$ in that case is relevant to $q$ iff there is a path from $d$ to $d_n$ that satisfies $q$ [67, 68], Crestani and Van Rijsbergen [23] and Crestani [21] assume that each indexing term $t \in T$ is a possible world. A document $d$ is true in $t$ if $t$ appears in $d$. A query $q$ is true in $t$ if $t$ appears in $q$. Crestani and Van Rijsbergen define $t_d$ as the closest term to the term $t$ where $d$ is true.

Crestani and Van Rijsbergen use the imaging technique to move probabilities from the terms that do not appear in $d$ to the terms that appear in $d$. They build a new probability distribution $P_d$ from the original distribution $P$ by imaging on $d$. Crestani and Van Rijsbergen have shown that the logical uncertainty $U(d \rightarrow q)$ can be estimated as follows:

Nie et al. [70] define the fuzzy accessibility relations between two possible worlds and the fuzzy truth value of a proposition in a possible world in order to build an IR model. They represent a document $d$ as a possible world and a query $q$ as a logical sentence. They redefine the two functions $P^w(w^{\prime })$ and $w(s)$ as follows:

• The function $P^w(w^{\prime })$ estimates the fuzzy accessibility degree between two worlds $w$ and $w^{\prime }$, where $P^w(w)=1$.
  
• For any logical sentence $s$, the function $w(s)$ gives the fuzzy truth value of the sentence $s$ in the world $w$. This function is built based on $C_a(w)$, which represents the fuzzy truth value of an atomic proposition $a$ in a world $w$.
  

The retrieval decision is defined in the same way as in [67--69], whereas the logical uncertainty $U(d \rightarrow q)$ is defined as follows:

Before making some general remarks about using $\mathcal {PML}$ in IR, it is worth mentioning a work by Röelleke and Fuhr [80], who propose a four-valued extension of Kripke possible worlds semantics.

Even though using Kripke's semantics and its related imaging technique seem to be an interesting theoretical choice, IR models based on possible worlds and imaging have some disadvantages. These models are defined in the formal semantics side, and some operations have no direct correspondence in the formal language of the logic (syntax). For example, in a condition of the form $d \rightarrow q$, the connective $\rightarrow$ has no correspondence in the language of $\mathcal {PML}$. In addition, most models directly define the logical uncertainty $U(d \rightarrow q)$ without defining what the connective $\rightarrow$ refers to. This point could also be assumed as an advantage because it allows us to skip the task of defining $\rightarrow$.

It is also not easy to define the prior probability distribution on worlds $P(w)$ and what it refers to. Furthermore, defining accessibility relations and their related cost or distance measure is also a heavy task that needs a lot of study. Finally, experiments on large document collections show poor retrieval performance of these models [99].

Description Logic ($\mathcal {DL}$) is a family of languages to represent knowledge. It is more expressive than $\mathcal {PL}$ but it has more efficient reasoning than First-Order Logic ($\mathcal {FL}$). While the reasoning in $\mathcal {FL}$ is undecidable [84], there are some families of $\mathcal {DL}$ having polynomial time complexity [49], deterministic polynomial time [61], PSpace-complete [76], or even $O(n \log n)$ in the ALN family [88]. Before presenting the IR models that use $\mathcal {DL}$ as an underlying logical framework, we briefly introduce the formal language and semantics of $\mathcal {DL}$.

Chevallet and Chiaramella [16] build an IR model based on Conceptual Graphs (CGs). According to them, a document $d$ is a CG or, equivalently, a logical sentence in $\mathcal {FL}$, and a query $q$ is also a CG. The retrieval decision is as follows: $d$ is relevant to $q$ iff there exists a projection $\pi (q)$ of $q$ on $d$ or iff $d$ contains a sub-graph $\pi (q)$ that is a possible specialization of $q$. From the definition of the projection operation, the retrieval decision is equivalent to checking whether $d \le q$ or $\models [\Phi (d) \supset \Phi (q)]$, where $\Phi (x)$ corresponds to the logical sentence of the conceptual graph $x$.

The uncertainty of the retrieval decision $U(d \rightarrow q)$ is estimated using Kripke's semantics [50] or possible worlds semantics, where a document is a possible world and the accessibility relation between worlds is one of the four main operations on CGs (copy, restriction, simplification, or join). The cost of an accessibility relation between two worlds $w$ and $w^{\prime }$, denoted $P^w(w^{\prime })$, is related to the operation that causes this transformation from $w$ to $w^{\prime }$. Costs are arbitrarily assigned to each operation. The uncertainty $U(d \rightarrow q)$ is estimated as in [67], where $U(d \rightarrow q)$ is the cost of the path from $d$ to $d_n$ in which $d_n \le q$. To our knowledge, the model has not been tested on standard collections.

CG is a powerful formalism to express the content of documents and queries. However, it is hard to transform the content of documents and queries into CGs, and the projection operation is NP-complete [15].

Datalog is a predicate logic developed in database field. Probabilistic Datalog is an extension of deterministic Datalog using probability [34, 35]. The main difference between deterministic and probabilistic Datalog is that probabilistic Datalog defines probabilistic ground facts in addition to deterministic ground facts, which are classical predicates. Probabilistic ground facts have the form $\alpha g$, where $g$ is a deterministic ground fact (classical predicate) and $0\lt \alpha \le 1$ is the probability that the predicate $g$ is true. Deterministic ground facts are a special case of probabilistic ground facts, where $\alpha$ is always 1.

Ground facts are supposed to be probabilistically independent events. Assume that $\alpha _1 g_1$ and $\alpha _2 g_2$ are two probabilistic ground facts, where $g_1 \ne g_2$. Then, the following probabilistic ground fact is correct:

Probabilistic Datalog is used in IR [34, 52], where a document $d$ is a set of probabilistic ground facts of the form $\alpha \, \mathit {term}(d,t)$, which means that the document $d$ is indexed by the term $t$ and $\alpha$ is the probability that the predicate $\mathit {term}(d,t)$ is true or, equivalently, $\alpha$ is the probability that the document $d$ is about the term $t$. Fuhr [34] extends the previous definition of $d$, where the terms that index $d$ can be inferred using the predicate $\mathit {about}$ and the following inference rules:

The retrieval decision is defined as an inference rule. However, there are two main forms of the retrieval inference rule based on the connectives between query terms:

• Conjunction $q=t_1 \wedge t_2$:
  \[ q(D) :- \mathit {about}(D,t_1) \wedge \mathit {about}(D,t_2), \]
  where $D$ is a variable.
  
• Disjunction $q=t_1 \vee t_2$:
  \[ \begin{array}{l}q(D) :- \mathit {term}(D,t_1)\\ q(D) :- \mathit {term}(D,t_2). \end{array} \]
  
  

In [36], Fuhr and Röelleke propose a four-valued extension of probabilistic Datalog.

The main advantage of using probabilistic Datalog is the clear connection between IR and database, where probabilistic Datalog is an extension of deterministic Datalog that is used in the database. However, one must first assign probabilities to ground facts, which is not a simple task. For example, Röelleke et al. [81] proposed a modular way to estimate these initial probabilities. They introduced the relational Bayes operator to probabilistic relational algebra.

In this section, we focus on IR models that make use of fuzzy logic as an underlying logical framework. After presenting a few basic definitions related to fuzzy logic and fuzzy implications, we introduce the main application of fuzzy logic to IR.

Situation Theory ($\mathcal {ST}$) is a formal framework to model or represent information [9, 10]. Instead of studying whether a piece of information is true or false, $\mathcal {ST}$ studies what makes this piece of information true. According to $\mathcal {ST}$, information tells us that relations hold or not between objects. Therefore, the atomic information carriers are called infons, and an infon is a structure $\langle \langle R,a_1,\dots ,a_n;i \rangle \rangle$ that represents the information that the relation $R$ holds between the objects $a_1,\dots ,a_n$ if $i=1$, or it does not hold if $i=0$. A situation is a partial description of the world, or it can be defined as a set of infons [45]. A situation $s$ supports an infon $f$, denoted $s \models f$, if $f$ is made true by $s$ or, equivalently, if $f$ can be deduced from the set of infons of $s$.

$\mathcal {ST}$ generalizes a set of situations having common characteristics into a type of situation. The notation $s:A$ refers to the fact that the situation $s$ is of the type $A$. A constraint is a relation between two types of situation, $A$ and $A^{\prime }$, denoted $A \Rightarrow A^{\prime }$. A constraint such as $A \Rightarrow A^{\prime }$ means that the occurrence of a situation $s:A$ implies the existence of a situation $s^{\prime }:A^{\prime }$. Uncertainty is represented as a conditional constraint, denoted $A \Rightarrow A^{\prime } | B$, which means that the constraint $A \Rightarrow A^{\prime }$ is fulfilled under some conditions $B$, where $B$ itself can be a type of situation.

Lalmas and Rijsbergen [53] build an IR model–based on $\mathcal {ST}$. According to them, a document $d$ is a situation and a query $q$ is an infon or a set of infons. The document $d$ is relevant to a query $q$ iff $d$ supports $q$, denoted $d \models q$. The uncertainty of the previous retrieval decision is estimated based on the conditional constraints

Huibers and Bruza [45] present two examples, a Boolean model and coordination-level matching model, on how to build the situations that represent documents and queries, and what the retrieval decision $d \models q$ concretely means. Huibers and Bruza also use $\mathcal {ST}$ to define the aboutness relation between a document and a query in order to build a meta IR model capable of formally comparing IR models.

The main disadvantage of $\mathcal {ST}$-based IR models is the difficulty of automatically building meaningful infons for representing the content of documents and queries. Moreover, uncertainty needs to be defined in a less abstract way in order to build an implementable version of these models.

Default logic is used to represent semantic relations between objects, for example, synonymy and polysemy. It is used in IR to represent some background knowledge or thesauri knowledge. Default logic defines a special inference mechanism called default rules, denoted $\frac{\varphi : \beta }{\psi }$, which means that, in a particular context, if $\varphi$ is true and $\lnot \beta$ cannot be inferred, then infer $\psi$.

Positioning is the process of changing a logical sentence using default rules. For example, assume a logical sentence $s$ is $a \wedge b$, where $a$ and $b$ are propositions. Assume the following default rule $\frac{a : \lnot c}{e}$, where $c$ and $e$ are also propositions. The positioned sentence $s^{\prime }$ of $s$, according to the previous default rule, is $a \wedge b \wedge e$.

Hunter [46] uses default logic to build an IR model. A document $d$ is a clause or, equivalently, a conjunction of literals, where each literal is either a proposition or its negation. Each indexing term corresponds to a proposition. A query $q$ is a logical sentence. The retrieval decision is the material implication where $d$ is relevant to $q$ iff $d \supset q$.

Semantic relations between terms are represented through default rules. For example, assume the following default rule:

The uncertainty of $d \supset q$ is estimated through finding the positioned version $d^{\prime }$ of $d$ using the set of default rules, where $d^{\prime } \supset q$. Default logic–based IR models have the ability to build context-dependent models and to qualitatively define the logical uncertainty $U(d \rightarrow q)$. However, these models suffer from some disadvantages. The automatic learning of default rules is not an easy task and is error prone. In addition, there is no quantitative measure of uncertainty.

During the last decade, several approaches have tackled the issue of employing logic in information retrieval. One of the interests in using logic for IR is the fact that the results are predictable and explanatory. For example, Description Logic is explicitly used to formalize knowledge in medical IR systems [13, 77]. Belief revision [54] is being investigated to cope with vague queries. Logic is also used inside the IR system for specific tasks, for example, ranking [82], query representation [58], estimation of query difficulty [57], and meta-fusion of classical IR [39]. Zerarga and Djouadi [98] present the generalization that the logical approach provides of various IR models. Zuccon et al. [100] present logical imaging as a quantum theory interpretation, using the $K$ kinematic operator.

Concerning the evaluation of logical IR models, there have been many recent attempts to apply logical IR models to large-scale document collections. It is important to recall that the first IR models were not able to manage such collections and were evaluated on smaller datasets. For example, Picard and Savoy [74] (Section 3.3) applied their model to the corpus CACM⁹, which is a very small collection of documents (only 3,204). With respect to the $\mathcal {PML}$-based IR models (Section 4), Amati and Kerpedjiev [4] have conducted preliminary experiments on Nie's model [67, 68] (Section 4.2) by applying it to a small test collection (103 documents); they conclude that the model has a retrieval performance comparable to vector-space and probabilistic models. The imaging-based model of Crestani and Van Rijsbergen [23] (Section 4.3) has been tested with large [24] and small [25] document collections. In [24], Crestani et al. review challenges in front of applying the imaging-based model to a large document collection (a part of TREC4¹⁰, about 165,000 documents), where they especially mention the problem of probability transfer or obtaining $P_d$ based on $P$. In general, the results are not promising, maybe because of the simplifications that they are obliged to do in order to obtain an operational version of their imaging-based model. Nie et al. [70] (Section 4.4) applied their model to the corpus CACM, which is a very small collection of documents (only 3,204). Thus, it is not possible to draw clear conclusions from their study. Since reasoning is complex in $\mathcal {FL}$, there are very few attempts to implement $\mathcal {FL}$-based IR models. For example, the model of [16] (Section 5.2) is tested only on a small set of documents, where their conceptual graphs are manually obtained.

Losada and Barreiro [60] were among the first to apply their logical model (Section 3.2) to a large TREC collection (about 170,000 documents). They express queries (topics) as DNF sentences as follows: each part of the query (i.e., title, description, narrative) corresponds to one clause, and $q$ is $\mathit {title} \vee \mathit {description} \vee \mathit {narrative}$. Also, documents are expressed by means of DNF logical sentences. The authors show that the retrieval effectiveness of their model is better than the one of the classical tf.idf-based vector space model. However, they do not compare their model to other IR models, and they do not experiment with other document collections. They also claim that most of the gain in performance comes from building a rather complex document and query representation. Zuccon et al. [99] apply the logical imaging–based model of Crestani and Van Rijsbergen [23] (Section 4.3) also on TREC collections and show that imaging-based IR models, as presented in [23], have a retrieval performance lower than the performance of some classical IR models. Recently, Abdulahhad et al. [3] applied their model (Section 3.4) to large-scale and standard corpora, for example, ImageCLEF¹¹ and TREC. The authors showed that their IR model performs better than classical IR models, for example, the vector space model [89], probabilistic model [79], language models [75], and information model [18]. One important conclusion of these recent works is that it is possible for logical models to have operational and effective implementations.

In last 20 years, logic has been extensively employed as a formal language to define models for applications related to information and knowledge management.

In 1998, Tim Berners Lee claimed that the semantic web could be designed based on logic¹². Since then, efforts have been spent to implement this idea and the definition of ontologies and of reasoning mechanisms on them relies on formal languages based on various kinds of logic: for example, OWL-DL¹³ (based on description logic) and SWRL¹⁴. In 2010, John F. Sowa published a paper that analyses “the role of logic and ontology in language and reasoning” [90]. Sowa asserts that “projects in artificial intelligence developed large systems based on complex versions of logic, yet those systems are fragile and limited in comparison to the robust and immensely expressive natural languages.” He proposes an analysis that can lead “to a more dynamic, flexible, and extensible basis for ontology and its use in formal and informal reasoning.”

More recently, the knowledge graph has been defined as a means to represent knowledge and to reason on it. This term was introduced by Google with reference to the knowledge base that the company defined to enhance its search engine with semantic information. Since then, many companies have engaged in defining their own knowledge graphs. As pointed out in Bellomarini et al. [11], “The reasoning core of a KGMS needs to provide a language for knowledge representation and reasoning (KRR)” that should “achieve a careful balance between expressive power and complexity.” To this aim, the authors describe the VADALOG language, which they have defined.

Logic also plays an important role in ontology-based IR systems. These are hybrid systems in which the query is first represented in the logical format of the knowledge base, typically description logic [14, 32]. The output of the logical inference is then used to feed a simple bag-of-words IR system. These proposals show that at least logic can be used outside of typical IR models. We think there may be a new research path that should study the fusion of ontology logic deduction with the IR model instead of just gluing two different systems: deductive on one side and statistical on the other.

Hence, we believe that formal logics are useful tools to formally represent and integrate knowledge in IR models and also useful to reproduce the inferential nature of the retrieval process. These are the main motivations beyond the choice to study logic-based IR models and to build new models. The above synthesis shows the current interest of logic and IR based on the more recent findings and research developments in different and strongly related applications.