Steven Schockaert
email: s.schockaert@cs.cardiff.ac.be

Henri Prade
email: prade@irit.fr

Interpolative and extrapolative reasoning in propositional theories using qualitative knowledge about conceptual spaces

Keywords:

Many logical theories are incomplete, in the sense that non-trivial conclusions about particular situations cannot be derived from them using classical deduction. In this paper, we show how the ideas of interpolation and extrapolation, which are of crucial importance in many numerical domains, can be applied in symbolic settings to alleviate this issue in the case of propositional categorization rules. Our method is based on (mainly) qualitative descriptions of how different properties are conceptually related, where we identify conceptual relations between properties with spatial relations between regions in Gärdenfors conceptual spaces. The approach is centred around the view that categorization rules can often be seen as approximations of linear (or at least monotonic) mappings between conceptual spaces. We use this assumption to justify that whenever the antecedents of a number of rules stand in a relationship that is invariant under linear (or monotonic) transformations, their consequents should also stand in that relationship. A form of interpolative and extrapolative reasoning can then be obtained by applying this idea to the relations of betweenness and parallelism respectively. After discussing these ideas at the semantic level, we introduce a number of inference rules to characterize interpolative and extrapolative reasoning at the syntactic level, and show their soundness and completeness w.r.t. the proposed semantics. Finally, we show that the considered inference problems are PSPACE-hard in general, while implementations in polynomial time are possible under some relatively mild assumptions.

Introduction

Symbolic approaches to knowledge representation typically start from a finite set of natural language labels, which are associated to atomic propositions (in propositional settings), to predicates (in first-order settings), or to atomic concepts (in description logics). The meaning of these labels is then expressed implicitly by encoding how the corresponding propositions are related to each other using a logical theory. Clearly, such a logical theory can only capture a small fraction of the actual meaning of the labels at the cognitive level. Formalizing commonsense reasoning then boils down to developing principled approaches to extend or refine logical inference, such that the conclusions that can be derived from a logical theory become, in some way, closer to what we infer at the cognitive level. Some approaches to non-monotonic reasoning [START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF], for instance, deal with exceptions by assuming that rules only apply to typical instances of the concepts involved or are only valid in normal situations, even though these notions of typicality and normality are not explicitly expressed at the symbolic level. Essentially, such approaches are non-monotonic because the factual knowledge they work on is incomplete: we may know that Tweety is a bird, but not that it is a penguin. Later observations may enrich our factual knowledge base, necessitating a revision of some of the assumptions that were made (e.g. Tweety can fly). As another form of commonsense reasoning, in this paper we look at techniques for dealing with a lack of generic knowledge. For the ease of presentation, we will assume that generic knowledge is expressed as a set of propositional rules. We are then interested in situations where factual knowledge is, in principle, complete, but where none of the given rules applies to the situation at hand. For instance, we may know that it is advisable to rest (i) when feeling nauseated and having a high fever, and (ii) when feeling nauseated without any fever, but not have any information about what is advisable in case of nausea with a mild fever.

Similarity-based reasoning Humans can often cope with such a lack of knowledge by drawing analogies, or by resorting to knowledge about similar situations [START_REF] Collins | The logic of plausible reasoning: A core theory[END_REF][START_REF]The Analogical Mind: Perspectives from Cognitive Science[END_REF]. This observation has led to a number of theories of approximate reasoning, which are mainly based on the premise that from similar conditions we can draw similar conclusions. Most notably, a large number of fuzzy set based approaches have been proposed that build on the idea that the more a situation is compatible with the fuzzy labels in the antecedent of a rule, the more it should be compatible with the fuzzy labels in its consequent. Such rules, called gradual rules in [START_REF] Dubois | What are fuzzy rules and how to use them[END_REF], are based on a measure of similarity that is implicit in the definition of the membership functions of the fuzzy labels. Related to gradual rules, certainty rules [START_REF] Dubois | What are fuzzy rules and how to use them[END_REF] rather encode that the more similar a situation is to the fuzzy labels in the antecedent of a rule, the more certain that the consequent holds. Some related approaches avoid the use of fuzzy sets and rather encode similarity assessments in an explicit way (e.g. [START_REF] Sun | Robust reasoning: integrating rule-based and similarity-based reasoning[END_REF][START_REF] Dubois | A logical approach to interpolation based on similarity relations[END_REF][START_REF] Medina | Similarity-based unification: a multi-adjoint approach[END_REF]). Given that a 1 and a → b hold, such methods allow to derive b with a certainty that depends on the degree of similarity sim(a, a 1 ).

Despite the intuitive appeal of similarity-based approaches, and their popularity in the context of control and classification problems, they face a number of difficulties when used for commonsense reasoning. First, quantitative similarity degrees can be hard to obtain in practice, a problem which is aggravated by the observation that similarity judgements are context-dependent [START_REF] Tversky | Features of similarity[END_REF][START_REF] Goldstone | Similarity in context[END_REF]. The quantitative nature of similarity degrees also makes it difficult to encode rules, e.g. exactly how similar should a given premise a 1 be to the antecedent of the rule a → b to derive b with a given certainty? Finally, similarity based methods tend to lack a principled way of dealing with conjunctions. For instance, assume that the rule a ∧ b → c and the facts a 1 and b 1 are known to hold, and moreover sim(a, a 1 ) = 0.6 and sim(b, b 1 ) = 0.4. To assess whether we can plausibly derive a 1 ∧ b 1 → c using similarity based reasoning, we would need to assess to what extent a 1 ∧ b 1 is similar to a ∧b. Usually, a truth-functional approach is assumed, assuming e.g. sim(a ∧b, a 1 ∧b 1 ) = min(sim(a, a 1 ), sim(b, b 1 )) or sim(a ∧ b, a 1 ∧ b 1 ) = sim(a, a 1 ) • sim(b, b 1 ). Such views, however, are hard to justify from a cognitive point of view.

Betweenness The aforementioned shortcomings of similarity-based reasoning seem closely related to the use of degrees.

A key observation is that in practice, similarity-based approaches are often used to implement a form of interpolation of symbolic rules: given the rules a 1 → b 1 and a 3 → b 3 , and a premise a 2 which is known to be between a 1 and a 3 , a conclusion is obtained between b 1 and b 3 . Interpolative inference, however, can also be implemented in a qualitative way, taking betweenness as primitive rather than similarity. Indeed, it suffices to know which propositions are conceptually between a 1 and a 3 and which propositions are between b 1 and b 3 . For instance, since a mild fever is conceptually between high fever and no fever, in the earlier example we conclude that resting is advised in case of nausea with a mild fever. This basic form of interpolative inference can then be further refined, depending on the kind of background information that is available about the conceptual relationships between the propositions (labels). For example, if we know that a 2 is closer to a 1 than to a 3 , we may insist that the conclusion should also be closer to b 1 than to b 3 . The idea of interpolating symbolic knowledge can also be extended to various forms of extrapolative inference, as is illustrated in the following example.

Example 1. Consider the following knowledge base, containing observations about the comfort level of different housing options: mansion → exclusive [START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF] villa ∧ suburbs → luxurious [START_REF] Collins | The logic of plausible reasoning: A core theory[END_REF] apartment ∧ suburbs → basic [START_REF]The Analogical Mind: Perspectives from Cognitive Science[END_REF] apartment ∧ centre → very-comfortable [START_REF] Dubois | What are fuzzy rules and how to use them[END_REF] Clearly, this knowledge base is incomplete. For instance, we have no information at all about the comfort level of a villa in the centre. However, from the rules that are provided, it seems reasonable to assume that villas are more comfortable than apartments (by comparing [START_REF] Collins | The logic of plausible reasoning: A core theory[END_REF] and ( 3)) and that housing in the centre is more comfortable than housing in the suburbs (by comparing (3) and ( 4)). As a form of extrapolative inference, this leads us to conclude that a villa in the centre would at least be as comfortable as a villa in the suburbs, i.e. either luxurious or exclusive. We may also wonder about apartments in the outskirts of the city. As living in the outskirts is conceptually between living in the centre and living in the suburbs, from [START_REF]The Analogical Mind: Perspectives from Cognitive Science[END_REF] and (4) we may reasonably assume, as a form of interpolative inference, that the comfort level of an apartment in the outskirts would be between basic and very-comfortable.

Objectives of the paper The aim of this paper is to develop a principled approach to interpolative and extrapolative reasoning, as a general way to avoid the use of degrees when dealing with incomplete generic knowledge. In particular, we address the following research questions:

1. How can interpolative and extrapolative inference be formalized? What are its computational properties and how can automated inference procedures be implemented? 2. What is the nature of the background knowledge that is needed to support interpolative and extrapolative reasoning? 3. What is the semantic justification for interpolation and extrapolation? While most approaches to non-monotonic reasoning have a principled semantic foundation, typically based on the notion of preferred worlds [START_REF] Shoham | A semantical approach to nonmonotonic logics[END_REF][START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF] or the idea of stable models [START_REF] Reiter | A logic for default reasoning[END_REF][START_REF] Gelfond | The stable model semantics for logic programming[END_REF], this is to a much lesser extent the case for current methods that deal with incompleteness of rule bases.

The underlying idea is that among all possible refinements of a given knowledge base we favour those which are most regular, an intuition which will be formalized using the theory of conceptual spaces [START_REF] Gärdenfors | Conceptual Spaces: The Geometry of Thought[END_REF]. This theory posits that natural language labels can be identified with a convex region in a particular geometric space -called a conceptual space -whose dimensions correspond to cognitively meaningful qualities. Using conceptual spaces, notions such as betweenness can be given a clear geometric interpretation, which allows us to derive a semantic characterization of various interpolative and extrapolative inference relations. It is important to note, however, that although conceptual spaces are crucial to justify our approach, in practical applications, we do not actually require that the conceptual space representations of properties are available. In particular, the inference mechanism itself will only require qualitative knowledge about how the conceptual representations of labels are spatially related. For instance, to support a basic interpolative inference relation, it is only required that we know which labels are conceptually between which other labels. Furthermore note that this form of commonsense reasoning will actually be monotonic: increasing the rule base may allow us to refine earlier conclusions, but will never violate them. In contrast, in the setting of non-monotonic reasoning, increasing the factual knowledge may lead us to consider different rules to be applicable, as more specific rules may override more general ones.

Depending on the considered application, the required qualitative knowledge can be provided by an expert or it can be derived automatically using data-driven techniques. In the first case, an expert may choose to manually encode some rules, and rely on interpolation or extrapolation to avoid the need for a complete specification of the considered domain (e.g. explicitly enumerating the comfort level for all housing types and all location types). The resulting inference relation would be guaranteed to provide sound conclusions, although for those parts of the domain that were not explicitly modelled by the expert, available information may be less precise (but not trivial). In the second case, where data-driven techniques are used to obtain background information about the conceptual relationship of different labels (e.g. by analysing documents from the web), the aim is rather to generate plausible conclusions from imperfect conceptual background knowledge. In this way, we can combine the rigour of a logic-based framework with the flexibility of data-driven methods. The commonsense aspect of the approach thus lies in the possibility to go beyond classical deduction by taking advantage of structural domain knowledge that has been induced from data, without resorting to purely statistical techniques as in [START_REF] Speer | Analogyspace: reducing the dimensionality of common sense knowledge[END_REF].

Organization The paper is structured as follows. After discussing related work in Section 2, we present a high-level overview of our approach in Section 3. Section 4 subsequently discusses in more detail how qualitative spatial descriptions of conceptual spaces can be used to encode the conceptual relationship of different atomic properties. Next, in Section 5 we investigate how conceptual relations between atomic properties can be leveraged to conceptual relations between unions and intersections of properties (represented as sets of vectors of properties), and how the latter conceptual relations can be used to refine a given rule base at the semantic level. In Section 6 we then focus on the syntactic level: we introduce a set of inference rules and show that they are sound and complete w.r.t. the semantics from Section 5. Section 7 analyses the computational complexity of interpolative and extrapolative reasoning and presents an implementation method. In Section 8 we present some further thoughts on how to apply our method in practice, and in particular on the question of how to handle inconsistencies that are introduced by our method. We present our conclusions and a number of directions for future work in Section 9. Finally, note that this paper forms a substantially extended and revised version of [START_REF] Schockaert | Qualitative reasoning about incomplete categorization rules based on interpolation and extrapolation in conceptual spaces[END_REF]. Among others, we now provide a complete characterization of extrapolative inference and include the idea of comparative distance (whereas only the interpolative inference relation was characterized in [START_REF] Schockaert | Qualitative reasoning about incomplete categorization rules based on interpolation and extrapolation in conceptual spaces[END_REF]). We moreover present an implementation method, as well as the proofs.

Related work

Our work is clearly related to existing approaches in cognition and knowledge representation that are based on a spatial representation of knowledge. However, our approach also touches upon several other domains, including non-monotonic reasoning, similarity-based reasoning, regularization in machine learning, and qualitative physics. We briefly clarify the relationship with each of these domains.

Spatial representations of meaning

One of the central motivations of this paper is to approach commonsense reasoning by abandoning the idea that atomic propositions are independent from each other, in favour of a view which allows them to be conceptually related in a way that cannot be fully expressed at the logical level. Although atomic propositions are traditionally assumed to be independent, several 20th century philosophers have argued against such a view. Wittgenstein [START_REF] Wittgenstein | Some remarks on logical form[END_REF] was among the first to realize that sometimes we need more than a purely syntactic approach to logic, considering that atomic logical formulas may exclude each other while they are not contradictory. A statement such as place P is green at time T and place P it is blue at time T is treated as nonsensical by Wittgenstein rather than false, where he writes "It is, of course, a deficiency of our notation that it does not prevent the formation of such nonsensical constructions, and a perfect notation will have to exclude such structures by definite rules of syntax" [START_REF] Wittgenstein | Some remarks on logical form[END_REF]. In the same spirit, Carnap [START_REF] Carnap | A basic system of inductive logic, part 1[END_REF] uses the notion of an attribute space to group predicates of the same type. An attribute space is an abstract representation of a certain domain. For instance, the attribute space of colours consists of all (infinitely many) colour instances. In practice, these attribute spaces are usually described using a finite set of labels, which correspond to predicates at the logical level. By thus partitioning the predicates into separate attribute spaces, one can restrict interpretations to those that make exactly one predicate true from each attribute space, for any given individual. Quine [START_REF] Quine | Natural kinds, in: Ontological Relativity and Other Essays[END_REF] uses the related notion of a quality space to characterize similarity, putting forward the view that similarity cannot be defined in logical terms, and thus requires a deeper representation of atomic propositions. These works have led to the more recent development of conceptual spaces [START_REF] Gärdenfors | Conceptual Spaces: The Geometry of Thought[END_REF] by Gärdenfors, in an attempt to use the idea of a spatial representation of meaning to tackle problems in artificial intelligence (AI), among others. Conceptual spaces will be discussed in more detail in Section 4.

Apart from the work on conceptual spaces, the idea of assuming a spatial representation to reason about concepts also underlies [START_REF] Lehmann | The EGG/YOLK reliability hierarchy: semantic data integration using sorts with prototypes[END_REF], where an approach to integrate heterogeneous databases is proposed based on spatial relations between concepts. This approach starts from the observation that types from one database may not have an exact counterpart in another database. Conceptual relations between types are therefore considered which express e.g. that all typical instances of type A belong to type B but some instances of type A may be outside B. Such relations can formally be modelled as egg/yolk relations, which are a form of qualitative spatial relations between ill-defined spatial regions. Somewhat related, in [START_REF] Schockaert | Solving conflicts in information merging by a flexible interpretation of atomic propositions[END_REF] we presented a general method for merging conflicting propositional knowledge bases coming from different sources, based on the view that different sources may have a slightly different understanding of a given label. The different ways in which such a label may be understood are encoded in terms of four primitive relations that essentially correspond to qualitative spatial relations between (unknown) geometric representations of the labels. Although the kind of spatial relations encountered in these existing works are mainly mereotopological, qualitative spatial reasoning about betweenness is an active topic of research [START_REF] Clementini | A reasoning system of ternary projective relations[END_REF][START_REF] Hahmann | Multidimensional mereotopology with betweenness[END_REF].

Non-monotonic reasoning

In general, several facets of commonsense reasoning have been extensively studied within the field of AI. Of particular interest is the work on System P for reasoning about rules with exceptions [START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF]. In this approach, a non-monotonic consequence relation is defined by encoding axiomatically how new rules may be derived from existing rules. In particular, the non-monotonic consequence relation |∼ is defined by the following inference rules: where ≡ and | denote equivalence and entailment in classical logic, respectively. Intuitively, α| ∼β means that in normal situations where α holds, it is also the case that β holds. The normative approach by System P about how a non-monotonic consequence relation should behave has been very influential in the field of non-monotonic reasoning. While the purpose of our paper is not to study non-monotonic consequence relations, our approach does resemble System P in that our goal is also to produce new rules, which are appropriate to a given situation. However, whereas System P is concerned with finding the most specific rules that are compatible with our (incomplete) knowledge about the situation at hand, in interpolative and extrapolative reasoning there is no genuine issue of incompleteness at the factual level. Rather, we are interested in situations where the given situation is not explicitly covered by a rule base, but is intermediate between, or analogous to situations that are covered.

Reflexivity α| ∼α

Similarity-based reasoning

Somewhat related, several authors have studied similarity-based consequence relations which are based on the intuition that α approximately entails β iff every model of α is similar to some model of β [START_REF] Ruspini | On the semantics of fuzzy logic[END_REF][START_REF] Dubois | A logical approach to interpolation based on similarity relations[END_REF][START_REF] Vetterlein | A logic of the similarity with prototypes and its relationship to fuzzy logic[END_REF]. In [START_REF] Dubois | Similarity versus preference in fuzzy set-based logics[END_REF], for instance, a similarity-based consequence relation is contrasted with the consequence relation from System P, revealing that similaritybased reasoning satisfies monotonicity and most of the axioms of System P, but not the cut rule. More generally, a large number of authors have proposed systems for approximate, similarity-based reasoning within the field of fuzzy set theory.

Most of these works are based on Zadeh's generalized modus ponens [START_REF] Zadeh | A theory of approximate reasoning[END_REF] (but see [START_REF] Schwartz | A system for reasoning with imprecise linguistic information[END_REF] for an early example of a more qualitative approach), which allows us to derive a fuzzy restriction on the value of variable Y from the knowledge that if X is A then Y is B and X is A ′ with A, A ′ and B fuzzy sets. The basic idea is that the more A is similar to A ′ , the more the inferred restriction on Y will be close to B. When this idea is applied to a set of parallel rules, such that the fuzzy sets in the antecedents of the rules overlap, it leads to a form of interpolative reasoning. Furthermore, several authors have proposed methods to interpolate fuzzy rule bases in general, i.e. without requiring overlap of the fuzzy sets; we refer to [START_REF] Perfilieva | Interpolation of fuzzy data: Analytical approach and overview[END_REF] for a recent overview. While these techniques are also about interpolating rules, they differ from our approach in a number of ways. First, they are mostly restricted to uni-dimensional, numerical domains, and they require that quantitative representations of symbolic labels be available in the form of fuzzy sets. Furthermore, they treat logical connectives, such as conjunctions in the antecedent, in a truth-functional (and therefore heuristic) way.

In [START_REF] Sheremet | Comparative similarity, tree automata, and diophantine equations[END_REF], a logic called CSL is introduced which has a construct A ⇔ B denoting all objects that are more similar to instances of concept A than to instances of concept B. The qualitative nature of this logic brings it closer to the approach we present in this paper. As it is based exclusively on closeness, and not on other aspects of spatial localization such as being in between, CSL is not directly suitable as a basis for interpolative or extrapolative reasoning. Interestingly, however, as a result of this restriction, CSL can be described using a preferential semantics [START_REF] Alenda | Preferential semantics for the logic of comparative concepts similarity[END_REF].

Regularity

In the propositional setting, the idea of interpolation and extrapolation has been studied in [START_REF] Dupin De Saint-Cyr | Belief extrapolation (or how to reason about observations and unpredicted change)[END_REF], but from a rather different angle. In particular, the paper discusses how the belief that certain propositions hold at certain moments in time can be extended to beliefs about other moments in time, using persistence assumptions as a starting point. Nonetheless, as in our paper, the main idea is to use general meta-principles to find those completion(s) of a knowledge base that are most regular in some sense.

The idea of regularity can also be found in work on analogical proportions. An analogical proportion is an expression of the form a : b :: c : d which reads as a is to b as c is to d. If a, b, c and d are binary propositions, this can be formalized as (a [START_REF] Miclet | Handling analogical proportions in classical logic and fuzzy logics settings[END_REF]). In [START_REF] Prade | Classification by means of fuzzy analogy-related proportions -a preliminary report[END_REF], an approach to classification is outlined which uses the view that, as a form of regularity, the more of the condition attributes of three training items form an analogical proportion with the condition attributes of the item to be classified, the more it becomes likely that also the decision attribute should form an analogical proportion. Using connectives from multi-valued logic, analogical proportions can be defined for graded propositions, which allows us to extend this idea to numerical attributes. In [START_REF] Prade | Completing rule bases in symbolic domains by analogy making[END_REF], an extrapolative inference mechanism has been proposed which is based on such analogical proportions between graded proportions. The latter technique can be seen as a special case of the approach we develop in this paper. In this paper, however, we also consider forms of interpolative and extrapolative reasoning that are not based on analogical proportions, and the proposed techniques are moreover not restricted to linearly ordered domains. More generally, the idea of regularity appears in various forms in learning settings. In graph regularization [START_REF] Zhou | A regularization framework for learning from graph data[END_REF], for instance, the desire for regularity is even made explicit in the form of a graph which connects instances that should receive a similar classification. In other approaches, the idea of regularity is implicit in the choice of the underlying classification functions that are allowed (e.g. being restricted to hyperplanes in the case of support vector machines), and is thus imposed to avoid overfitting. As an example of another domain where the idea of regularity surfaces, [START_REF] Gérard | Ranking alternatives on the basis of generic constraints and examples: a possibilistic approach[END_REF] presents an approach to derive a preference ordering, starting from a set of generic preferences. To choose a specific ordering among all those satisfying the constraints, the principle of minimal specificity from possibility theory is adopted as a way to avoid introducing any irregularities that have not been explicitly specified as constraints.

→ b ≡ c → d) ∧ (b → a ≡ d → c) (see
The notion of matrix abduction, proposed in [START_REF] Abraham | Analysis of the talmudic argumentum a fortiori inference rule (kal vachomer) using matrix abduction[END_REF] is also related to our work in its use of regularity as a criterion to complete missing values, although it operates at a lower-level representation. Specifically, consider a matrix whose rows correspond to objects and whose columns correspond to binary features, such that exactly one entry of the matrix is '?', corresponding to a missing value, and all the other entries are 0 or 1. Then [START_REF] Abraham | Analysis of the talmudic argumentum a fortiori inference rule (kal vachomer) using matrix abduction[END_REF] proposes to choose the missing value such that the regularity of the matrix is maximized. Specifically, a partial order relation is induced from both of the possible completions of the matrix, and the completion which is favoured is the one whose associated partial order relation is most natural in some sense. Note that, somewhat related, in abductive reasoning for causal diagnosis, it is also common to favour the simplest explanations (e.g. preferring single fault diagnoses to explain observed symptoms).

Qualitative physics

Finally, there is some resemblance between the inference procedure presented in this paper and the early work on qualitative reasoning about physical systems [START_REF] Forbus | Qualitative process theory[END_REF][START_REF] Kuipers | Qualitative simulation[END_REF], which deals with monotonicity constraints such as "if the value of x increases, then (all things being equal) the value of y decreases". Our inference procedure differs from these approaches as the domains we reason about do not need to be linearly ordered. Moreover, in the special case of linearly ordered domains, we assume no prior information about which partial mappings are increasing and which are decreasing.

Overview of the approach

In this section, we introduce some notations and basic concepts that will be used throughout the paper. We also present the main intuitions of our approach at an informal level.

Let A 1 , . . . , A n be finite sets of labels, where each set A i corresponds to a certain type of properties 1 (e.g. colours), and the labels of A i correspond to particular properties of the corresponding type (e.g. red, green, orange). The labels in A i are assumed to correspond to jointly exhaustive and pairwise disjoint (JEPD) properties. Note that each element (a 1 , . . . , a n ) from the Cartesian product A = A 1 × • • • × A n then corresponds to a maximally descriptive specification of the properties that some object or situation may satisfy. We furthermore assume that A i ∩ A j = ∅ for i = j. We will refer to the sets A i as attribute domains, and to their elements as attributes or, when used in a propositional language, as atoms.

We consider propositional rules of the form β → γ , where β and γ are propositional formulas, built in the usual way from the set of atoms A 1 ∪ • • • ∪ A n and the connectives ∧ and ∨. Note that we do not need to explicitly consider negation, as the negation of an atom a ∈ A i corresponds to the disjunction of the atoms in A i \ {a}. We say that an element (a 1 , . . . , a n ) ∈ A is a model of a formula (or a rule) α, written (a 1 , . . . , a n ) | A α if the corresponding propositional interpretation {a 1 , . . . , a n } is a model of α in the usual sense, where we see propositional interpretations as sets containing all atoms that are interpreted as true. For formulas (or rules or sets of rules) α 1 and α 2 , we say that α 1 entails α 2 , writ-

ten α 1 | A α 2 if for every ω ∈ A, ω | A α 1 implies ω | A α 2 .
Note that the notion of entailment we consider is classical entailment, modulo the assumption that the propositions in each set A i are JEPD.

Example 2. Consider the following attribute domains:

A 1 = {row-house 1 , semi-detached 1 , bungalow, villa, mansion, bedsit, studio, one-bed-ap, two-bed-ap, three-bed-ap, loft, penthouse} A 2 = {row-house 2 , semi-detached 2 , detached, apartment} A 3 = {very-small, small, medium, large, very-large} A 4 = {basic, comfortable, very-comfortable, luxurious, exclusive} where A 1 lists the housing types that are possible in the given context, A 2 provides a coarser description of some of these housing types, and A 3 and A 4 contain the labels that are used to describe housing sizes and comfort levels respectively. Note that subscripts are used for the housing options row-house and semi-detached to ensure that different attribute domains are disjoint. When there is no cause for confusion, we will omit these subscripts. The following set of rules R provides a partial specification of how these attribute domains are related to each other:

bungalow → medium bungalow → detached (5) mansion → very-large mansion → detached (6) large ∧ detached → lux large ∧ row-house → comf (7)
small ∧ detached → bas ∨ comf mansion → excl [START_REF] Tversky | Features of similarity[END_REF] where some labels are abbreviated for the ease of presentation. For example (villa, detached, large, lux) is a model of each of these rules. Note that the only conclusions that can be derived from R are more or less trivial, e.g.

R |

A villa → very-small ∨ small ∨ medium ∨ large ∨ very-large

(9) R | A (small ∨ large) ∧ detached → basic ∨ comfortable ∨ luxurious (10)
Note that (9) follows from our assumption that the labels in an attribute domain are exhaustive.

Commonsense inference

A rule base R over the atoms in A usually only provides an incomplete specification of how the given attribute domains are related to each other. We are interested in refining the available knowledge in R using a number of generic metaprinciples. To this end, we will make use of background knowledge about the conceptual relationship of different formulas, which we assume to be encoded in a set of assertions Σ (to be formalized in Section 6). We are then interested in defining a consequence relation ⊢ that extends the entailment relation | A (i.e. supraclassicality). Specifically, we assume that the following inference rule is valid:

R | A β → γ (R, Σ) ⊢ β → γ (S)
The first meta-principle we consider is that intermediate conditions should lead to intermediate conclusions.

For instance, given that both large and small detached houses have a comfort level that is between basic and luxurious, we derive that also medium detached houses should have a comfort level between these bounds. More generally, if a propositional formula β is conceptually between the formulas β 1 and β 2 , the idea of interpolative inference is that whatever we can derive from β should be conceptually between what we can derive from β 1 and what we can derive from β 2 . The exact nature of this conceptual betweenness will be formalized in the following sections, but intuitively β is conceptually between β 1 and β 2 if β has all the features that β 1 and β 2 have in common. We could say, for instance, that a bistro is conceptually between a bar and a restaurant, or that a studio is conceptually between a bedsit and an apartment. In ecology, we may consider that taiga is between tundra and temperate-forest. We could take the view that the painting style of Renoir is conceptually between the painting styles of Monet and Manet.

To encode information about betweenness at the syntactic level, we use a modality ✶, i.e. the formula β 1 ✶ β 2 is true whenever a situation holds which is conceptually between a situation satisfying β 1 and a situation satisfying β 2 (or alternatively, when talking about concepts, β 1 ✶ β 2 is true for instances that are between β 1 and β 2 ). Typically, it will not be possible to have a precise definition of β 1 ✶ β 2 , as, in fact, our logical language may not be rich enough to precisely capture exactly those situations. However, in practice, we may obtain knowledge about upper and lower approximations of

β 1 ✶ β 2 .
We write Σ ⊢ γ → β 1 ✶ β 2 to denote that everything which satisfies γ is conceptually between β 1 and β 2 , and Σ ⊢ β 1 ✶ β 2 → γ to denote that anything which is conceptually between β 1 and β 2 should definitely satisfy γ . Example 3. It is not the case that all lofts are conceptually between a three-bedroom apartment and a penthouse (e.g. a small loft with only one bedroom), so loft → three-bed-ap ✶ penthouse does not hold. However, we do have trivially that three-bed-ap ∨ penthouse → three-bed-ap ✶ penthouse Conversely, however, some lofts are between a three-bedroom apartment and a penthouse, so we cannot remove the disjunct loft in the consequent of the following implication three-bed-ap ✶ penthouse → three-bed-ap ∨ loft ∨ penthouse Note that in the considered domain, there are no apartments with more than three bedrooms (with the possible exception of penthouses), hence three-bed-ap, loft and penthouse exhaustively cover all situations that are between a three-bedroom apartment and a penthouse.

On the other hand, we may consider that all studios are between bedsits and one-bedroom apartments. Under this view,

we should be able to derive the following rules from Σ :

bedsit ∨ studio ∨ one-bed-ap → bedsit ✶ one-bed-ap bedsit ✶ one-bed-ap → bedsit ∨ studio ∨ one-bed-ap

Using the binary modality ✶, we can define the following interpolative inference rule:

(R, Σ) ⊢ β 1 → γ 1 (R, Σ) ⊢ β 2 → γ 2 Σ ⊢ β * → β 1 ✶ β 2 Σ ⊢ γ 1 ✶ γ 2 → γ * (R, Σ) ⊢ β * → γ * (I)
A diagrammatic representation of this interpolation principle is shown in Fig. 1(a): given two rules β 1 → γ 1 and β 2 → γ 2 , we derive a rule which applies to a situation β * which is intermediate between β 1 and β 2 . The conclusion γ * of that rule is required to exhaustively cover all situations that are intermediate between γ 1 and γ 2 .

The second meta-principle states that analogous changes in the condition of a rule should lead to analogous changes in the conclusion.

Let us write β 1 , β 2 to denote the change that is needed to convert a specification compatible with β 1 into a specification compatible with β 2 . The intuition will be that β 1 , β 2 determines a direction-of-change. In contrast to betweenness, this notion of direction is not symmetric, e.g. while two-bed-ap, three-bed-ap denotes the direction of an increasing number of bedrooms, three-bed-ap, two-bed-ap denotes a decreasing number. Given a third formula β 3 , we are then interested in those situations that can be obtained by changing a situation compatible with β 3 in the direction specified by β 1 , β 2 . In particular, we will write β 3 ✄ β 1 , β 2 for the formula that covers all such situations. For example, we could consider that progressive rock differs from hard rock by having less standard song structures and arrangements, while keeping the same instruments. Then heavy-metal ✄ hard-rock, prog-rock would cover all music genres that use heavy metal instruments and timbres, but less standard song structures and arrangements. This would include all progressive metal, as well as some instances of avant-garde metal, among others. In biology, we may consider that the difference between dog to coyote is analogous to the difference between cat and leopard, or to the difference between cat and lynx, which we could encode as coyote → dog ✄ cat, leopard and coyote → dog ✄ cat, lynx respectively. Note in particular that we do not take into account the amount of change: while we may consider that the change from cat to leopard is bigger than the change from dog to coyote, the direction of change is the same.

As for betweenness, we will mainly be interested in approximating β 3 ✄ β 1 , β 2 rather than finding an exact definition, i.e. we will be looking for propositional formulas that imply, and that are implied by

β 3 ✄ β 1 , β 2 .
Example 4. The change from a bedsit to a studio essentially corresponds to an increase in size and comfort. In this sense, such a change is similar to the change from a two-bedroom apartment to a three-bedroom apartment, or even to a penthouse. We may consider, for instance:

Σ ⊢ two-bed-ap ∨ three-bed-ap ∨ penthouse → two-bed-ap ✄ bedsit, studio Σ ⊢ two-bed-ap ✄ bedsit, studio → two-bed-ap ∨ three-bed-ap ∨ loft ∨ penthouse
Only the direction of the change is taken into account here, and not the amount of change. For instance, we might have Σ ⊢ one-bed-ap ∨ two-bed-ap ∨ three-bed-ap ∨ penthouse → one-bed-ap ✄ one-bed-ap, two-bed-ap Note that the meaning of . , . by itself cannot be expressed at the syntactic level, i.e. . ✄ . , . is treated as a ternary modality. Extrapolative inference can then be formalized as follows:

(R, Σ) ⊢ β 1 → γ 1 (R, Σ) ⊢ β 2 → γ 2 (R, Σ) ⊢ β 3 → γ 3 Σ ⊢ β * → β 1 ✄ β 2 , β 3 Σ ⊢ γ 1 ✄ γ 2 , γ 3 → γ * (R, Σ) ⊢ β * → γ * (E)
A diagrammatic representation is given in Fig. 1(b). In this case, three rules β 1 → γ 1 , β 2 → γ 2 and β 3 → γ 3 are available, and we are interested in deriving conclusions about a fourth situation β * which differs from β 1 as β 3 differs from β 2 . The conclusion γ * which is derived exhaustively covers all situations that differ from γ 1 as γ 3 differs from γ 2 .

Finally, we assume that the consequence relation ⊢ is deductively closed:

(R, Σ) ⊢ β 1 → γ 1 (R, Σ) ⊢ β 2 → γ 2 {β 1 → γ 1 , β 2 → γ 2 } | A β 3 → γ 3 (R, Σ) ⊢ β 3 → γ 3 (D)
Σ ⊢ (large ∨ medium ∨ small ∨ very-small) ∧ row-house → (large ∧ row-house) ✄ large ∧ det, small ∧ det Σ ⊢ comf ✄ lux, bas ∨ comf → bas ∨ comf then (E) yields (R, Σ) ⊢ (large ∨ medium ∨ small ∨ very-small) ∧ row-house → bas ∨ comf ( 11
)
from which we obtain using (D) that (R, Σ) ⊢ medium ∧ row-house → bas ∨ comf . Indeed, the rule in [START_REF] Reiter | A logic for default reasoning[END_REF] plays the role of β 1 → γ 1 from the definition of (D), whereas the rule β 2 → γ 2 is trivial.

At this point it may not be clear whether the inference relation defined by (S), (I), (E) and (D) always behaves according to intuition, nor what the implications are at the semantic level of adopting (I) and (E). To this end, in the following sections, we will develop a semantic counterpart of the inference relation ⊢, which will clarify the nature of the modalities ✶ and ✄ , and will allow us to implement decision procedures for reasoning tasks of interest. A crucial issue that will be discussed in detail is the interaction between the aforementioned modalities on the one hand, and logical conjunction on the other hand, e.g. discussing under which conditions (α

1 ∧ β 1 ) ✶ (α 2 ∧ β 2 ) is equivalent to (α 1 ✶ α 2 ) ∧ (β 1 ✶ β 2 ).
The principles (I) and (E) allow us to refine a rule base R by exploiting background knowledge about the conceptual relationship of labels from the same attribute domain. This background knowledge is of a qualitative nature. Extrapolative reasoning, for instance, is based on the idea of direction of change, but does not take the amount of change into account.

An analogical proportion such as a : b :: c : d, on the other hand, not only expresses that the change from a to b goes in the same direction as the change from c to d, but also that the amount of change between a and b is the same as the amount of change between c and d [START_REF] Prade | Analogical proportions: another logical view[END_REF]. To take information about the amount of change into account, and thus generalize analogical reasoning -making it also more cautious when necessary -we will use expressions such as β 1 ✄ [λ,µ] β 2 , β 3 where 0 λ µ < +∞. Intuitively, this formula covers all situations that can be obtained by changing β 1 in the same direction as the change from β 2 to β 3 , such that the amount of change is between λ and µ times as large as the amount of change between β 2 and β 3 . This allows us to make inferences which are more precise in cases where suitable information about the amount of change is available. For example, knowing that the amount of change between dog and coyote is approximately the same as the amount of change between cat and lynx, the latter relationship is more useful than the relationship between cat and leopard if we want to derive knowledge about coyotes from knowledge about dogs.

The most straightforward use of this generalization is to express whether the amount of change from β 1 should be smaller, equal, or larger than the amount of change from β 2 to β 3 . In particular, β 1 ✄ [1,1] β 2 , β 3 corresponds to the solution X that makes β 1 : X ::

β 2 : β 3 a perfect analogical proportion, while β 1 ✄ [0,1[ β 2 , β 3 and β 1 ✄ ]1,+∞[ β 2 ,
β 3 express amounts of change that are smaller and larger, respectively, than the amount of change from β 2 to β 3 . Note that β 1 ✄ [0,+∞[ β 2 , β 3 corresponds to β 1 ✄ β 2 , β 3 . Also note that in the aforementioned cases, the approach remains entirely qualitative. Other choices for the intervals [λ, µ] may give the approach a more numerical flavour, and would mainly be useful in scenarios where the conceptual relationships are obtained using data-driven techniques.

For τ a non-empty subset of [0, +∞[, Principle (E) can be refined to

(R, Σ) ⊢ β 1 → γ 1 (R, Σ) ⊢ β 2 → γ 2 (R, Σ) ⊢ β 3 → γ 3 Σ ⊢ β * → β 1 ✄ τ β 2 , β 3 Σ ⊢ γ 1 ✄ τ γ 2 , γ 3 → γ * (R, Σ) ⊢ β * → γ * (E')
Along similar lines, for σ a non-empty subset of [0, 1], we consider expressions of the form β 1 ✶ σ β 2 to put constraints on the relative closeness to β 1 and β 2 . Specifically, β 1 ✶ [0,0.5[ β 2 corresponds to those situations between β 1 and β 2 that are closer to β 1 than to β 2 . Note that β 1 ✶ [0,0.5[ β 2 is a refinement of the construct β 1 ⇔ β 2 from CSL [START_REF] Sheremet | Comparative similarity, tree automata, and diophantine equations[END_REF], as betweenness is not required in CSL, only comparative closeness. Similarly, β 1 ✶ ]0.5,1] β 2 corresponds to situations that are closer to β 2 than to β 1 , and β 1 ✶ [0.5,0.5] β 2 to situations that are exactly halfway. When data-driven techniques are used, other intervals may again be useful. In scenarios where labels can be assumed to be equidistant, we may also know e.g. that small → very-small ✶ [0.25,0.25] very-large and large → very-small ✶ [0.75,0.75] very-large, where the idea is that medium is halfway between very-small and very-large and small is halfway between very-small and medium.

Principle (I) can be refined to (R, Σ) ⊢ β 1 → γ 1 (R, Σ) ⊢ β 2 → γ 2 Σ ⊢ β * → β 1 ✶ σ β 2 Σ ⊢ γ 1 ✶ σ γ 2 → γ * (R, Σ) ⊢ β * → γ * (I') Example 6.
Consider again the setting of Example 5, and assume that a villa is conceptually halfway between a bungalow and a mansion, and that a large house is conceptually halfway between a medium house and a very-large house. We then get

Σ ⊢ villa → bungalow ✶ [0.5,0.5] mansion (12)
Σ ⊢ medium ✶ [0.5,0.5] very-large → large [START_REF] Gärdenfors | Conceptual Spaces: The Geometry of Thought[END_REF] which allows us the obtain the refined conclusion (R, Σ) ⊢ villa → large using (I') and (D). Alternatively, we could assume that a villa is conceptually closer to a bungalow than to a mansion, by assuming that

Σ ⊢ bungalow ∨ villa → bungalow ✶ [0,0.5[ mansion Together with Σ ⊢ medium ✶ [0,0.5[ very-large → medium ∨ large we would then find R ⊢ villa → medium ∨ large.

Mappings between attribute domains

At the semantic level, a rule base R can be seen as a mapping between sets of vectors of attributes. In particular, assume that all the labels in the antecedents of the rules in R belong to the attribute domains B 1 , . . . , B s and that the labels in the consequents belong to C 1 , . . . , C k . The rule base R can then equivalently be expressed as a function f R from subsets of

B = B 1 × • • • × B s to subsets of C = C 1 × • • • × C k , defined for X ⊆ B as f R (X) = Y ∈ 2 C R | A (x 1 ,...,x s )∈X s i=1 x i → (y 1 ,...,y k )∈Y k i=1 y i where A = A 1 × • • • × A n and {A 1 , . . . , A n } = {B 1 , . . . , B s } ∪ {C 1 , . . . , C k } as before.
It is not hard to see that this function indeed expresses the same knowledge as the rule base R. Furthermore, there exists a single

Y * ∈ 2 C such that f R (X) = Y * and R | A (x 1 ,...,x s )∈X s i=1 x i → (y 1 ,...,y k )∈Y * k i=1 y i Example 7.
Consider again the rules base from Example 2. We have that B = A 1 × A 2 × A 3 , as no rule refers to comfort levels in its antecedent, and C = A 2 × A 3 × A 4 , as only the coarser housing types of A 2 are referred to in the consequent of rules. We find that a small detached villa is either basic or comfortable:

f R (villa, det, small) = (det, small, bas), (det, small, comf )

Indeed, from small ∧ detached → bas ∨ comf It follows that small ∧ detached ∧ villa → (bas ∨ comf ) ∧ small ∧ detached
from which we can already conclude f R (villa, det, small) ⊆ (det, small, bas), (det, small, comf )

It is furthermore clear that there are no rules in R which could be used to further refine f R ({(villa, det, small)}).

Similarly, we find that a bungalow is detached and medium-sized, while we find no restrictions on the possible comfort levels:

f R (bun, x, y) , x ∈ A 2 , y ∈ A 3 = (det, medium, z) z ∈ A 4
We may see f R as an approximate (i.e. incomplete) model of a given domain, which may be refined as soon as new information becomes available. In particular, for two 2 B → 2 C functions f and f ′ which are monotone w.r.t. set inclusion,

we say that f is a refinement of f ′ , written f f ′ , iff ∀X ⊆ B. f (X) ⊆ f ′ (X) (14)
This idea of using monotone set-valued functions to describe approximate models is closely linked to the theory of Scott domains; see e.g. [START_REF] Laymon | Using Scott domains to explicate the notions of approximate and idealized data[END_REF] for an elaboration of this idea. At the semantic level, completing the rule base R boils down to refining the corresponding function f R . In our approach, such refinements will be based on meta-knowledge about the nature of the relationship between B and C. This will lead us to replace f R by the largest refinement, w.r.t. , which is compatible with the imposed meta-knowledge. In particular, as will become clear below, Principles (I) and (E) amount to refine f R by imposing some form of monotonicity, whereas (I') and (E') amount to refine f R by imposing a form of linearity. As could be expected, the meta-knowledge underlying (I') and (E') is stronger than the meta-knowledge underlying (I) and (E).

Formalization using conceptual spaces

The approach sketched in Section 3 requires information about how the labels of an attribute domain are conceptually related to each other. Provided that this information is available, inference can be carried out purely at the symbolic level. However, to justify the inference procedure, and to provide an adequate semantics for it, we need to be precise on how relationships such as betweenness should be interpreted. To this end, we assume that the cognitive meaning of the attributes can be represented geometrically, as convex regions in a conceptual space. Conceptual relationships can then be given a clear spatial interpretation, as will be discussed in Section 4.1. Taking advantage of this link with conceptual spaces, Section 4.2 subsequently reviews some opportunities for the acquisition of conceptual relations. Finally, Section 4.3 presents the idea of regular mappings between conceptual spaces as a basis for interpolative and extrapolative reasoning.

Geometric modelling of attribute domains

The theory of conceptual spaces [START_REF] Gärdenfors | Conceptual Spaces: The Geometry of Thought[END_REF] is centred around the assumption that the meaning of a natural property can be adequately modelled as a convex region in some geometric space. Formally, a conceptual space is the Cartesian product

Q 1 ו • •× Q m of
quality dimensions, each of which corresponds to an atomic, cognitively meaningful feature, called a quality.

A standard example is the conceptual space of colours, which can be described using the quality dimensions hue, saturation and intensity. Labels to describe colours, in some natural language, are then posited to correspond to convex regions in this conceptual space, a view which is closely related to the ideas of prototype theory [START_REF] Gärdenfors | Reasoning about categories in conceptual spaces[END_REF]. The label red for instance will be represented by the set of points whose hue is in the spectrum normally associated with red, whose saturation is sufficiently high, and whose intensity is neither too high nor too low. Note that while e.g. red may be an atomic property at the symbolic level, at the cognitive level it is defined in terms of more primitive notions. Quality dimensions may be continuous or discrete, and can even be finite. In practice, however, it is common to identify conceptual spaces with Euclidean spaces [START_REF] Gärdenfors | Reasoning about categories in conceptual spaces[END_REF], and to define cognitive similarity in terms of Euclidean distance. We will also adopt this simplifying view throughout the paper, although part of the discussion readily generalizes to more general spaces. 2Now consider again the example of housing types. A conceptual space to represent housing types would have a large number of dimensions, relating to shape, size, colour, texture, etc. Each house that exists in the world will correspond to one specific point in this conceptual space. Conversely, however, there may be points in that conceptual space which do not correspond to structures that can be physically realized, or that would not be recognized as houses (e.g. a building structure of 20 km long and 1 cm wide). Each attribute from the domain A 1 corresponds to a convex region in the conceptual space, where intuitively, e.g. the region corresponding to villa corresponds to those building structures that are more similar to prototypical villas than to prototypical instances of the other attributes in A 1 .

In general, each attribute domain A i thus corresponds to a partition of some conceptual space in convex regions, where each attribute of A i corresponds to a partition class. As some regions of conceptual spaces may correspond to types of instances that do not exist in the real world, the number of partition classes may, in principle be higher than the number of attributes in A i . We write reg(x) to denote the convex region that corresponds to label x. For example, reg(three-bed-ap) represents all sections of building structures that could be classified as three-bedroom apartments. This set will contain both points that correspond to actual apartments (which exist somewhere in the world) and possible apartments (which may in principle be built one day).

This conceptual space representation of the attributes is considerably richer than what can be described at the symbolic level, and therefore also allows for richer forms of inference. However, in most application domains, it is not reasonable to assume that such representations are available. Moreover, the precise representation of a property in a conceptual space strongly depends on the considered context and may be subjective. Usually, however, it is assumed that a particular conceptual space representation can be obtained from a generic representation by appropriately rescaling the quality dimensions Fig. 2. Modelling betweenness and parallelism between regions. [START_REF]Formalizing conceptual spaces[END_REF]. Note that this observation implies that also similarity judgements may differ across contexts and people, as rescaling the dimensions may influence the relative Euclidean distance between points. For instance, while apples are usually considered to be closer to tomatoes than to chocolate, in the context of desserts, they may be closer to chocolate (e.g. because both can be used in cakes). To alleviate these issues, we will rely on (mainly) qualitative knowledge about the spatial relationship of different properties. Such qualitative knowledge may be easier to obtain, and because the spatial relations that will be considered are invariant under affine transformations (such as rescaling the quality dimensions), they are more robust against changes in context and person. In particular, such relations are not affected by rescaling of the quality dimensions, although they would still depend on context changes that introduce additional quality dimensions.

For each attribute domain A i , we assume that information is available about betweenness and parallelism of the conceptual space representation of its attributes. For example, we may intuitively think of a studio to be between a bedsit and a one-bedroom apartment. In the domain of music genres, we may consider that the change from hard-rock to progressive-rock is parallel to the change from heavy-metal to progressive-metal, and that progressive-rock is between hard-rock and avantgarde. The notions of betweenness and parallelism are straightforwardly defined for points in Euclidean spaces. In particular, let us write bet(p, q, r) to denote that q lies between p and r (on the same line), and par(p, q, r, s) to denote that the vectors --→ pq and -→ rs point in the same direction. The fact that point q is between points p and r means that for every point x it holds that d(q, x) max(d(p, x), d(r, x)), and in particular, that whenever p and r are close to a prototype of some concept, then q is close to it as well. In this sense, we may see bet(p, q, r) as a way to express that whatever natural properties p and r have in common, p and q have them in common as well (identifying points in a conceptual space with instances). On the other hand, par(p, q, r, s) intuitively means that to arrive at s, r needs to be changed in the same way as p needs to be changed to arrive at q, i.e. at the qualitative level, p is to q as r is to s (although the amount of change may be different).

The notions of betweenness and parallelism, which are defined for points, need to be extended to regions, in order to describe relationships between attributes. As is well known, this can be done in different ways [START_REF] Billen | On the Move to Meaningful Internet Systems[END_REF]. We will consider the following two notions of betweenness for regions A, B, and C (in a given Euclidean space):

bet( A, B, C ) iff ∃q ∈ B.∃p ∈ A.∃r ∈ C .bet(p, q, r) (15) bet( A, B, C ) iff ∀q ∈ B.∃p ∈ A.∃r ∈ C .bet(p, q, r) (16)
In particular, if A and C are convex regions, bet( A, B, C ) holds if B overlaps with the convex hull of A ∪ C , whereas bet( A, B, C ) holds if B is included in this convex hull. These two notions of betweenness are illustrated in Fig. 2(a), where bet( A, B 1 , C ), bet( A, B 1 , C ) and bet( A, B 2 , C ) hold, but not bet( A, B 2 , C ). Note in particular that both relations are reflexive w.r.t. the first two arguments, in the sense that e.g. bet( A, A, C ) holds, as well as symmetric, in the sense that e.g. bet( A, B, C ) ≡ bet(C , B, A). However, transitivity does not necessarily hold for regions, e.g. from bet( A, B, C ) and bet(B, C , D) we cannot infer that bet( A, B, D); a counterexample is depicted in Fig. 3(a). 3 In the terminology of rough set theory [START_REF] Pawlak | Rough Sets: Theoretical Aspects of Reasoning about Data[END_REF], bet and bet correspond to upper and lower approximations of betweenness. The underlying idea is that, given our finite set of labels, we may not be able to exactly describe the convex hull of two regions A and B. All we can do, then, is to list all labels which are completely included in the convex hull (i.e. define the lower approximation of the convex hull), and all labels which have a non-empty intersection with the convex hull (i.e. define the upper approximation of the convex hull). In the following, for the ease of presentation we will often identify labels with the corresponding regions, writing e.g. bet(a, b, c) for bet(reg(a), reg(b), reg(c)).

Example 8. In the domain of housing types, we may consider that we have bet(three-bed-ap, loft, penthouse) but not bet(three-bed-ap, loft, penthouse). Note that this corresponds to what was expressed at the syntactic level in Example 3. For regions A, B, C and D (in a given Euclidean space), two notions of parallelism will be considered:

par( A, B, C ; D) iff ∃s ∈ D.∃p ∈ A, ∃q ∈ B, ∃r ∈ C .∃λ 0. - → rs = λ • --→ pq par( A, B, C ; D) iff ∀s ∈ D.∃p ∈ A, ∃q ∈ B, ∃r ∈ C .∃λ 0. - → rs = λ • --→ pq
For parallelism, the role of the convex hull is replaced by a notion of conical extension, which is illustrated in Fig. 2(b). In particular, if par( A, B, C ; D) holds, some point in D differs from some point in C in the same direction that some point in B differs from some point in A. In the scenario of Fig. 2(b), this means that D overlaps with the shaded area. Likewise, when par( A, B, C ; D) holds, D is included in the shaded area of Fig. 2(b). For all regions A, B and C , we have that par( A, B, C ; C ) holds (and thus also par( A, B, C ; C )), as well as par( A, B, A; B). However, as for betweenness, transitivity does not hold, as is illustrated in Fig. 3(b).

Example 9. We may consider that the following relations hold (cf. Example 4)

par(bedsit, studio, two-bed-ap; loft) par(bedsit, studio, two-bed-ap; three-bed-ap)

In other words, for every point s in reg(three-bed) we can find points p ∈ reg(bedsit), q ∈ reg(studio) and r ∈ reg(two-bed-ap)

such that --→ pq is parallel to - →
rs. In other words, every three-bedroom apartment differs from some two-bedroom apartment in (qualitatively) the same way as some studio differs from some bedsit. Similarly, we have that some (but not all) lofts differ from some two-bedroom apartment in the same way that some studio differs from some bedsit.

As a refinement of bet(p, q, r), we may put constraints on the distance ratio d(p,q) d(p,r) , where d denotes the Euclidean distance. Note that distance ratios for points on the same line are preserved under affine transformations. In particular, for σ a subset of [0, 1], we consider the following relations:

bet σ (A, B, C ) iff ∃q ∈ B.∃p ∈ A.∃r ∈ C .bet(p, q, r) ∧ ∃λ ∈ σ .d(p, q) = λ • d(p, r) (17) bet σ (A, B, C ) iff ∀q ∈ B.∃p ∈ A.∃r ∈ C .bet(p, q, r) ∧ ∃λ ∈ σ .d(p, q) = λ • d(p, r) (18) Clearly, bet = bet [0,1] and bet = bet [0,1]
. Other notable cases are σ = [0.5, 0.5], when ( 17)-( 18) express that B is halfway between A and C , σ =]0.5, 1], when ( 17)-( 18) express that B is closer to C than to A, and σ = [0, 0.5[, when ( 17)- [START_REF] Quine | Natural kinds, in: Ontological Relativity and Other Essays[END_REF] express that B is closer to A than to C . Note that we can only have bet [0,0] (reg(a), reg(b), reg(c)) if a = b since labels from the same attribute domain are assumed to be disjoint. A similar refinement of parallelism is possible, where for τ a subset of [0, +∞[, we define

par τ (A, B, C ; D) iff ∃s ∈ D.∃p ∈ A, ∃q ∈ B, ∃r ∈ C .∃λ ∈ τ . - → rs = λ • --→ pq ( 19
)
par τ (A, B, C ; D) iff ∀s ∈ D.∃p ∈ A, ∃q ∈ B, ∃r ∈ C .∃λ ∈ τ . - → rs = λ • --→ pq ( 20
)
In the particular case where τ = [1, 1], ( 19)-( 20) extend the idea of a parallelogram, whose relationship to the idea of analogical proportion is well known.

Acquiring conceptual relations

Regarding the applicability of our approach, an important question is how the required relational knowledge about conceptual spaces can be obtained, e.g. how do we find out that a studio is conceptually between a bedsit and a one-bedroom apartment? Depending on the specific application, different options may be available.

Manual encoding

In some domains, it is feasible to manually encode a complete qualitative description of a conceptual space. Most notably, this is the case for conceptual spaces that are uni-dimensional, for which it suffices to provide a ranking of the labels of interest. For instance, a conceptual space of housing sizes may be described by encoding that very-small < small < medium < large < very-large From this description, we immediately obtain that, for example, the relations bet(very-small, medium, large) and par(very-small, small, medium; very-large) hold. Note that in uni-dimensional domains, the relations bet and bet coincide when applied to labels of the same attribute domain (as these correspond to disjoint intervals), as do the relations par and par. In multi-dimensional domains, it may still be the case that providing a qualitative description is mainly a matter of ranking. The qualitative description of such simple multi-dimensional conceptual spaces can easily be modelled using a diagram. Fig. 4 provides an example of such a diagram, where lines define tuples that satisfy bet and parallel lines define tuples that satisfy par. For example, in the case of Fig. 4, we have that

par(2-bed-ap, 3-bed-ap, 2-bed-rowhouse; 3-bed-rowhouse)

As the formalization of such diagrams is straightforward, we will not discuss it in detail. However, it should be clear that a diagrammatic representation can only be obtained when some simplifying conditions are met. For example, in Fig. 4, it is tacitly assumed that bet = bet and par = par, and moreover that many transitivity and mixed transitivity properties are assumed for bet and par that do not hold in general (e.g. bet(a, b, c) ∧ par(b, c, d; e) ⇒ par(a, c, d; e)). While such diagrams can therefore not account for the full generality offered by the relations bet, bet, par and par, in simple domains, as the housing example of Fig. 4, they offer a convenient way of modelling our intuitions about the conceptual relationships that hold.

Natural language processing

A second possibility is to extract conceptual relations from natural language. In [START_REF] Turney | Measuring semantic similarity by latent relational analysis[END_REF], for instance, the idea of latent relational analysis was introduced, with the aim of identifying analogical proportions. As instances of par [START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF][START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF] correspond to analogical proportions, conceptual relations of this particular type can be obtained in the same way. The main idea is that two pairs of words are likely to be related analogously, i.e. form an analogical proportion, when the lexical contexts in which they co-occur are similar. For example, the words kitten and cat are found in sentences such as "a kitten is a young cat", while the words chick and chicken are found in sentences such as "a chick is a young chicken". From such observations, the analogical proportion kitten : cat :: chick : chicken can be discovered. Another technique for discovering analogical proportions from the web was proposed in [START_REF] Bayoudh | Evaluation of analogical proportions through Kolmogorov complexity[END_REF], estimating the strength of analogical proportions by converting co-occurrence statistics using Kolmogorov information theory. Instances of bet [0.5,0.5] (a, b, c) could be identified with analogical proportions of the form a : b :: b : c. In principle, instances of bet and bet can be discovered by applying general methods for extracting ternary relations from text [START_REF] Mcdonald | Simple algorithms for complex relation extraction with applications to biomedical IE[END_REF]. However, it is clear that the use of information extraction techniques to define the relations bet, bet, par and par will necessarily by highly heuristic, due to the inherent imperfection of such methods.

Data-driven techniques

If sufficient information is available about instances of concepts or properties, several data-driven approaches can be used, which directly take advantage of the geometric nature of the relations of interest. For instance, [START_REF] Gärdenfors | Reasoning about categories in conceptual spaces[END_REF] suggests to start from pairwise similarity judgements between instances, and use multi-dimensional scaling to obtain coordinates for them in a Euclidean space. Representations of concepts can then be obtained by determining the corresponding Voronoi tessellation, after which the conceptual relations of interest can be evaluated by straightforward geometric calculations. The number of dimensions of the resulting space can be freely chosen, where fewer dimensions lead to more conceptual relationships, as only the most prominent dimensions of the conceptual space are then taken into account. Thus, the lower the number of dimensions, the less cautious the resulting inference mechanism will be. In [START_REF] Schockaert | Interpolation and extrapolation in conceptual spaces: A case study in the music domain[END_REF], the feasibility of such an approach was demonstrated in the domain of music genres, using similarity judgements that were obtained indirectly using user-contributed meta-data from the website last.fm. 4Rather than starting from similarity judgements, [START_REF] Speer | Analogyspace: reducing the dimensionality of common sense knowledge[END_REF] suggests an approach based on singular value decomposition (SVD), which is a form of dimensionality reduction. Translated to our setting, the approach would start from a matrix where rows correspond to instances and columns correspond to binary features that these instances may or may not have. Instances are then represented in a high-dimensional space with one dimension for each feature, and coordinates are either 0 or 1, depending on whether the instance has the corresponding feature. Using SVD, a linear transformation is then determined which maps this high-dimensional space onto a space of lower dimension, with real-valued coordinates. As before, the resulting representations of the instance can be used to generate geometric representations of the concepts. Again we have that the chosen number of dimensions determines to what extent all quality dimensions, or only the most prominent ones are taken into account. Note that this latter approach offers an interesting connection between representations of concepts as sets of features and geometric representations, which also allows us to make the relationship between analogical proportions and parallelism explicit. In particular, assume that the analogical proportion a : b :: c : d holds for the instances a, b, c and d, and let their sets of features be denoted by A, B, C and D respectively. According to the formal definition of analogical proportion [START_REF] Prade | Analogical proportions: another logical view[END_REF][START_REF] Miclet | Handling analogical proportions in classical logic and fuzzy logics settings[END_REF], we have that A \ B = C \ D and B \ A = D \ C (where we write \ for set difference). From this observation, it is easy to see that the representations of a, b, c and d form a parallelogram in the initial, high-dimensional {0, 1}-valued space. Since, parallelograms are preserved under linear transformations, a, b, c and d will still form a parallelogram in the resulting conceptual spaces representation. Note that in principle, due to the lower number of dimensions, the conceptual space may contain more quadruples of instances that form a parallelogram than the initial space. These parallelograms intuitively correspond to pairs of instances that are analogical in all relevant aspects.

Alternatively, the SVD approach can also be applied when feature representations of concepts, rather than instances, are available. The concepts are then represented as points, and betweenness and parallelism of these points may be taken to be indicative of betweenness and parallelism of the unknown representations of the concepts as regions.

Example 10. Consider a rule base about red wines. From a web page about red wines 5 we learn the following knowledge

beaujolais → low-tan ∧ light-body inexpensive ∧ burgundy → low-tan ∧ light-body bardolino → low-tan ∧ light-body valpolicella → low-tan ∧ light-body inexpensive ∧ bordeaux → low-tan ∧ med-body chianti → low-tan ∧ med-body rioja → low-tan ∧ med-body merlot → (low-tan ∨ mid-tan) ∧ med-body mid-range ∧ burgundy → low-tan ∧ med-body inexpensive ∧ cabernet-sauvignon → low-tan ∧ med-body mid-range ∧ bordeaux → mid-tan ∧ med-body above-average ∧ cabernet-sauvignon → mid-tan ∧ med-body zinfandel → (mid-tan ∨ high-tan) ∧ (med-body ∨ full-body) shiraz → (mid-tan ∨ high-tan) ∧ (med-body ∨ full-body) high-end ∧ bordeaux → high-tan ∧ full-body high-end ∧ burgundy → high-tan ∧ full-body high-end ∧ cabernet-sauvignon → high-tan ∧ full-body barolo → high-tan ∧ full-body barbaresco → high-tan ∧ full-body brunello-di-montalcino → high-tan ∧ full-body low-tan ∧ light-body → light-red low-tan ∧ med-body → med-red mid-tan ∧ med-body → dark-red ∨ opaque high-tan ∧ full-body → opaque
Given the large number of wine types that exist, inevitably some types are not contained in this rule base. Let us consider, as an example, the wines Barbera and Bandol. From another web page about wine, 6 we extract information about wine-food pairings. For each listed wine type, we create a vector with one component for every listed food type. This component is set to 1 if the wine is mentioned as appropriate for the corresponding food type, and to 0 otherwise. Assuming that wine-food pairings are based on the taste of the wine, they may provide a valuable source of information about how different wines are related to each other. Using the SVD technique, we reduce the dimension of these vectors to a specified (typically somewhat arbitrary) number of abstract dimensions; in this example, we take 5 dimensions. As every wine type is then represented as a point in a 5-dimensional space, we can calculate which wines are between which other ones. In particular, if the cosine of the angle between cd is sufficiently close to 1, we assume that the change from wine a to wine b goes in the same direction as the change from wine c to wine d. In this way, we obtained that Barbera is between Chianti and Merlot (requiring the cosine to be at least 0.975). Given that these latter two wines, have either low or medium tannins, we can derive using interpolative inference that the same should hold for Barbera. Bandol, on the other hand, is not found to be between any two other types of wine. However, we do find that the following pairs (a, b), (c, d) correspond to parallel changes in wine type (again requiring the cosine to be at least 0.975):

(bandol, cabernet-sauvignon), (bordeaux, barolo) (bandol, zinfandel), (barolo, barbera) (bandol, zinfandel), (bordeaux, barbera) Given that the change from both Barolo and Bordeaux to Barbera is towards lower tannins, using extrapolative reasoning we derive that the amount of tannins in Bandol should not be smaller than the amount found in Zinfandel, i.e. we find that Bandol either has medium or high tannins.

Note that these data-driven approaches essentially use quantitative information to obtain a qualitative representation. One reason for not using a purely quantitative approach is that the available data is not likely to be sufficiently informative to build accurate conceptual space representations, but still allows us to discover information about qualitative relations between regions. In the case of Example 10, for instance, the quantitative representation we start with represents each concept as a point rather than a convex region. A second reason is that geometric calculations, such as determining convex hulls or Voronoi tessellations, are computationally expensive in high-dimensional spaces. When all we are interested in are spatial relations such as betweenness and parallelism, we can avoid to actually build the conceptual space, using a linear programming approach that was proposed in [START_REF] Schockaert | Interpolation and extrapolation in conceptual spaces: A case study in the music domain[END_REF]. Finally, as mentioned before, qualitative representations are invariant w.r.t. changes in the relative importance of the different quality dimensions.

Regular mappings between conceptual spaces

In this section, we show how the idea of interpolation and extrapolation can be formalized, and explicate the assumptions that warrant such forms of inference. We start from the functional view on rule bases suggested in Section 3.2. In particular, given the view of attribute domains as granular descriptions of conceptual spaces, we may look at mappings between attribute domains as granular descriptions of mappings between conceptual spaces.

Let A = A 1 × • • • × A n , B = B 1 × • • • × B s and C = C 1 × • • • × C k
be defined as before. As each A i , B j and C l correspond to a conceptual space, also A, B and C correspond to conceptual spaces, which we will denote by A, B and C respectively. Note that the set of quality dimensions underlying A is the union of the quality dimensions underlying the conceptual space representations of A 1 , . . . , A n and similar for B and C.

The mapping f R , induced by the knowledge base R, can then be seen as a mapping from subsets of B to subsets of C. The nature of this mapping will strongly depend on the nature of the rules involved. For example, let us consider the following rules 6 http://www.theworldwidewine.com/Wine_and_Food/This_wine_which_foods.php, accessed July 18th, 2011.

studio → small high-tannins ∧ fullbody → opaque museum ∧ has-live-animals → zoo large ∧ orchestra → symphony In these rules, the consequent is implied (only) by the meaning of the terms that appear in the antecedent, e.g. a museum which has live animals is called a zoo, by definition of the word zoo. As a result, we can make the assumption that the quality dimensions in C form a subset of the quality dimensions in B. This in turn means that there is a linear mapping m (viz. a projection) from B to the lower-dimensional space C. The (known) mapping f R can then be seen as an approximation of the (unknown) mapping m. Note that this means that there is an underlying functional dependency, e.g. every housing option will have a specific size, and every wine will have a specific degree of transparency. We will refer to rules of this kind as categorization rules.

Categorization rules can be contrasted with phenomenological rules, which encode observations about the world, e.g.:

morning → heavy-traffic autumn ∧ UK → rainy While in the four previous rules, the conclusion is the consequence of a categorical definition, in case of phenomenological rules, there is usually no underlying functional dependency: knowing the time of the day does not allow us to precisely know the amount of traffic, while knowing the date and location does not allow us to precisely know the amount of rain. Interestingly, a similar link between commonsense reasoning and functional dependencies was already pointed out in [START_REF] Davies | A logical approach to reasoning by analogy[END_REF].

The method we propose in this paper is based on the assumption that a rule base approximates a linear mapping, and thus only applies to categorization rules. However, it is worth noting that even for phenomenological rules, our method can often produce plausible conclusions when it is applied locally, e.g. while we should not conclude that there is heavy traffic at mid-day from the observations that there is heavy traffic in the morning and in the evening, it makes sense to conclude that there is heavy-traffic mid-morning if we know that there is heavy traffic in the early morning and late morning. Moreover, whether a rule classifies as phenomenological or not may depend on the underlying conceptual space representations that are assumed. For instance, the conceptual space representation of morning may in fact include a quality dimension for the amount of traffic, when mornings (in cities) and rush hour are considered to be so tied together that traffic jams become a characteristic feature of mornings (in a similar way that flying has become a characteristic feature of birds, even if it is not a defining feature). As a result of these considerations, when applying our method in practice, we would by default assume that it contains categorization rules. When this does not introduce any inconsistencies, the conclusions it produces are in some sense the most plausible ones, given the information that it available. When inconsistencies are introduced in the process, however, we may need to partially revise the assumption that the rules are categorization rules and/or that the conceptual relations we have are appropriate in the given context (i.e. take into account all the relevant features). While interpolative and extrapolative reasoning are monotonic forms of reasoning in principle, in practice they would be applied in a non-monotonic fashion, in the sense that adding more rules to a knowledge base may introduce inconsistencies, which would then lead us to apply interpolation and extrapolation more cautiously (or not at all). In Section 8, we will come back to the issue of how to deal with inconsistencies that are introduced by interpolative or extrapolative reasoning.

By taking the view that f R is the approximation of an unknown mapping m from points of B to points of C, we have for X ⊆ B that reg( f R (X)) ⊇ {m(p) | p ∈ reg( X)}, where we write reg( X) for the geometric representation of X as a region in B or C as before. More precisely, we take the view that the rule base R is compatible with some underlying mapping m in the sense that for each

X ⊆ B and Y ⊆ C it holds that R | A x∈ X s i=1 x i → y∈Y k i=1 y i ⇒ m * x∈ X reg(x) ⊆ y∈Y reg(y) ( 21
)
where the 2 B → 2 C mapping m * is defined as the point-wise extension of m.

The actual conceptual spaces B and C, and a fortiori the mapping m, are inaccessible in most applications. For instance, we cannot assume that a precise definition of a loft is available, or even an exhaustive enumeration of the qualities on which such a definition would depend. Moreover, using our finite vocabulary, we can only encode approximations of the mapping m, even in the face of complete knowledge. Let us write f for the most informative approximation that can be described using the available labels, i.e. f is the 2

B → 2 C mapping defined for X ∈ 2 B by f (X) = y ∈ C x ∈ X, m * reg(x) ∩ reg( y) = ∅
In other words, f R corresponds to the knowledge we actually have, while f corresponds to the maximal knowledge about the mapping m that we could hope to obtain.

(x) ∈ reg(n) ∪ reg(v), i.e. m * (reg(d)) = {m(x) | x ∈ reg(d)} ⊆ reg(n) ∪ reg(v).
Then the most precise mapping f that can be described using the vocabulary offered by B and C is such that f ({d}) = {n, v}. This means that the rule

d → n ∨ u ∨ v ∨ w could be refined to d → n ∨ v, but this knowledge is missing from R.
The mapping f is not available to us either; it corresponds to the semantic counterpart of a complete rule base, i.e. a rule base which entails all rules that are compatible with m. All we know about f is that it is a refinement of f R . Proposition 1. If R is compatible with m in the sense of [START_REF] Clementini | A reasoning system of ternary projective relations[END_REF], it holds that f f R .

Hence the goal of refining the knowledge base R corresponds, at the semantic level, to finding a mapping f R for which it is known that f f R f R . As all our domain knowledge is already encoded in R, a suitable f R = f R can only be obtained from meta-knowledge about the mapping f , or indirectly, from meta-knowledge about the mapping m. Here our restriction to categorization rules plays a key role, as it suggests that m should satisfy the properties of a linear transformation. This leads to the following postulates about the mapping m (p, q, r, s ∈ B, λ 0):

(bet1) bet(p, q, r) ⇒ bet(m(p), m(q), m(r)) (bet2) bet(p, q, r) ∧ d(p, q) = λ • d(r, q) ⇒ d(m(p), m(q)) = λ • d(m(r), m(q)) (par1) par(p, q, r, s) ⇒ par(m(p), m(q), m(r), m(s)) (par2) par(p, q, r, s) ∧ d(p, q) = λ • d(r, s) ⇒ d(m(p), m(q)) = λ • d(m(r), m(s))
In the following section, these postulates will be related to the commonsense inference principles that were introduced in Section 3.1. Specifically, it will become clear that the validity of Principle (I) is tied to (bet1), the validity of (E) is tied to (par1), the validity of (I') is tied to (bet1) and (bet2), and the validity of (E') is tied to (par1) and (par2).

Semantic characterization

To characterize interpolative and extrapolative inference, it is useful to note that knowledge can be described on three levels, in the given setting. First, there is the syntactic level, where new rules are produced from given sets of rules. This level will form the topic of Section 6. Second, there is the conceptual spaces level, where labels are represented as geometric regions, and knowledge takes the form of relations between geometric representations of properties and concepts, as was described in Section 4. Finally, there is an intermediate level which we will refer to as the semantic level, as it describes knowledge in terms of a standard propositional logic semantics. In particular, as explained in the beginning of Section 3, the elements of A take the role of interpretations of the propositional rules and formulas that we consider. This intermediate, semantic level will form the topic of the present section. In particular, at the semantic level, we are interested in approximating the mapping m between the conceptual spaces B and C, as well as relations such as betweenness and parallelism, using the vocabulary at hand. Typically, for a given conceptual space, a number of attribute domains D 1 , . . . , D l will be available, containing labels to refer to designated regions of the conceptual space. For the conceptual spaces B and C, these are respectively the attribute domains B 1 , . . . , B s and C 1 , . . . , C k . In general, the available attribute domains determine the level of granularity with which we can describe the underlying conceptual space.

The considered setting of three levels requires us to take into account some subtleties regarding the notion of logical consistency. A logical formula α was defined to be consistent w.r.t.

D 1 × • • • × D l if there exists an element d ∈ D 1 × • • • × D l
that corresponds to a propositional model of that formula. However, in general, we are not guaranteed that d actually corresponds to a non-empty region of the underlying conceptual space D. That is because some of the attribute domains may refer to the same quality dimensions. For example, while blue ∧ wine may be consistent at the propositional level, it corresponds to an empty set in the underlying conceptual space.

Let us call two attribute domains orthogonal if the sets of quality dimensions to which they refer are disjoint. In other words, two attribute domains are orthogonal if their elements refer to different features of a given domain. In particular, if two attribute domains A and B are orthogonal, for every a ∈ A and b ∈ B, a ∧ b will correspond to a non-empty set in the underlying conceptual space, which can be seen as the Cartesian product of reg(a) and reg(b). In other words, fixing the value of an attribute does not further restrict the possible values of the other attributes. For example, consider the rule large ∧ detached → lux from Example 2. The attribute domains A 2 and A 3 (corresponding to large and detached) are orthogonal to each other, but neither is orthogonal to the attribute domain A 4 (corresponding to lux). The concept of orthogonality is closely related to the idea of logical independence.

We call a set X ⊆ D 1 × • • • × D l realizable if we are guaranteed that X contains at least one element that corresponds to a non-empty region. If all of the attribute domains D 1 , . . . , D l are orthogonal, this is simply when X = ∅. In general, it may happen that some attribute domains are not orthogonal, but that these attribute domains are irrelevant w.r.t. X . In particular, we define a set X ↓i which essentially contains the elements from X that do not depend on the ith attribute domain:

(a 1 , . . . , a i-1 , a i+1 , . . . , a l ) ∈ X ↓i iff ∀x ∈ D i . (a 1 , . . . , a i-1 , x, a i+1 , . . . , a l ) ∈ X [START_REF] Hahmann | Multidimensional mereotopology with betweenness[END_REF] Now we can recursively define the notion of realizability. In particular, we say that X is realizable if (i) all attribute domains underlying X are orthogonal and X = ∅ or (ii) there exists an i such that X ↓i is realizable.

In this section, we will first analyse how conceptual relations can be defined between subsets of D 1 × • • • × D l . In Sections 5.1 and 5.2 we will look at betweenness and parallelism, before also taking comparative distance into account in Section 5.3. Finally, in Section 5.4, we will show how these relations can be used to refine the function f R , using the postulates (bet1), (bet2), (par1) and (par2) that were introduced in Section 4.3. Throughout the section, we will assume that the relations bet, bet, par and par are completely specified on the level of individual labels.

Betweenness

As explained in Section 4, our approach will start from available qualitative knowledge about the conceptual spaces underlying the attribute domains A 1 , . . . , A n . For three labels x, y, z ∈ A i , we may know for example that y is fully between

x and z, i.e. bet(reg(x), reg( y), reg(z)) holds, or that y is partially between x and z, i.e. bet(reg(x), reg( y), reg(z)) holds. Such betweenness information is sufficient for interpolative reasoning in situations where the antecedent of each rule consists of a single atom, taken from some fixed attribute domain B, and where the consequent of each rule consists of a single atom, taken from some fixed attribute domain C . To handle general rule bases, however, we need to lift the betweenness information we have about labels (i.e. atoms) to betweenness information about complex formulas. At the semantic level this means that we need information about the betweenness of subsets of Cartesian products First we focus on characterizing betweenness for elements of

D 1 × • • • × D l of attribute domains. Indeed, each element of D 1 × • • • × D l corresponds
D 1 × • • • × D l .
A central observation is that betweenness for a vector of labels cannot be reduced to betweenness for the labels in the respective components. In particular, notice that

when bet(a 1 , b 1 , c 1 ) and bet(a 2 , b 2 , c 2 ) hold, we do not necessarily have that (b 1 , b 2 ) is between (a 1 , a 2 ) and (c 1 , c 2 ). Indeed,
even for points in a Euclidean space of dimension two or more, betweenness in each dimension does not entail collinearity.

Here the intuition of bet and bet as upper and lower approximations of betweenness becomes important. In particular, while betweenness in each component is not sufficient, it is a necessary condition, hence the upper approximation of betweenness can still be defined as:

bet(a, b, c) iff ∀ j.bet(a j , b j , c j )

where we write e.g. a i for the ith component of vector a. To extend bet to vectors of labels, first note that when the attribute domains D 1 , . . . , D l are not orthogonal, we cannot provide any non-trivial guarantees as nothing is between the regions corresponding to a and c when one of these regions is empty. Hence bet(a, b, c) is false unless a = b = c. On the other hand, if the attribute domains D 1 , . . . , D l are all orthogonal, we define:

bet(a, b, c) iff (a = b) ∨ (b = c) ∨ ∃ j.(∀i = j.a i = b i = c i ) ∧ bet(a j , b j , c j ) (23)
Indeed, in the cases where a = b or b = c, we trivially have that bet(a, b, c) holds due to the fact that bet(p, p, q) holds for all points p and q. However, note that even in these trivial cases, we still need to require the orthogonality of the attribute domains D 1 , . . . , D l . In the case where a = b = c, on the other hand, we do have that bet(a, b, c) is trivially satisfied, even if all three regions are empty (as can easily be seen from the definition in ( 16)). The last disjunct in the right-hand side of ( 23) covers the general case, where we can only guarantee betweenness for a vector of labels if the vectors coincide in all but one component.

Example 12. The quality dimensions underlying attribute domains A 1 and A 2 from Example 2 clearly overlap. For example, it is not possible for a bungalow to also be an apartment, or for a loft to be a row-house. On the other hand, we may consider that attribute domains A 2 and A 3 are orthogonal. Note that this orthogonality holds irrespective of whether there actually exist apartments that are very-large. What is important is that nothing in the definition of an apartment prevents it from possibly being very-large. As a result, we can derive e.g. that bet (apartment, small), (apartment, large), (apartment, very-large)

holds but not e.g.

bet (bungalow, detached), (bungalow, semi-detached), (bungalow, row-house)

Now we move to betweenness of subsets of

D 1 × • • • × D l .
In particular, we will define sets bet( X 1 , X 2 ) and bet( X 1 , X 2 ) containing respectively those elements from D 1 × • • • × D l that are possibly partially between elements of X 1 and elements of X 2 , and those elements that are guaranteed to be completely between elements of X 1 and elements of X 2 . For bet this is straightforward: bet

(X 1 , X 2 ) = b | a ∈ X 1 , c ∈ X 2 , bet(a, b, c) (24)
The following proposition shows that this definition is indeed correct in the sense that it is compatible with the geometric notion of betweenness:

Proposition 2. Let X 1 , X 2 and Y be subsets of D 1 × • • • × D l . We have that bet reg(X 1 ), reg(Y ), reg(X 2 ) ⇒ Y ∩ bet(X 1 , X 2 ) = ∅
Note that we are slightly abusing notation here, writing bet both for a predicate which takes three regions as argument (as defined in (15)), and for a set which takes two subsets of D 1 × • • • × D l as argument (as defined in ( 24)).

To define bet, the realizability of the arguments X 1 and X 2 again comes into play. We define: bet

(X 1 , X 2 ) = Z ∪ b | a ∈ X 1 , c ∈ X 2 , bet(a, b, c) (25) ∪ 1 i l x∈D i (b 1 , . . . , b i-1 , x, b i+1 , . . . , b l ) | b (i) ∈ bet X ↓i 1 , X ↓i 2 with Z =        X 1 ∪ X 2 if X 1 and X 2 are realizable X 1 if only X 2 is realizable X 2 if only X 1 is realizable X 1 ∩ X 2 otherwise b (i) = (b 1 , . . . , b i-1 , b i+1 , . . . , b l )
The set Z intuitively corresponds to the trivial situations of betweenness a = b and b = c in [START_REF] Ruspini | On the semantics of fuzzy logic[END_REF]. If X 1 and X 2 are realizable, this means that all elements from X 1 and X 2 should be considered to be between X 1 and X 2 . If X 2 is realizable but not X 1 , we know that X 2 corresponds to a non-empty region in the corresponding conceptual space. The set X 1 , on the other hand, may or may not correspond to a non-empty region, the lack of realizability merely means that we cannot guarantee that reg( X 1 ) = ∅. In such a case, we cannot guarantee that the elements of X 2 are between X 1 and X 2 as this depends on whether or not X 1 corresponds to an empty region. However, it is not hard to see from (16) that bet(reg( X 1 ), reg( X 1 ), reg( X 2 )) holds regardless of whether reg( X 1 ) = ∅. The case where only X 1 is realizable is similar. If neither of X 1 and X 2 are realizable, betweenness can only be guaranteed for elements in X 1 ∩ X 2 , noting that reg( X 1 ∩ X 2 ) = ∅ as soon as one of reg( X 1 ) = ∅ or reg( X 2 ) = ∅ holds. The second component in the right-hand side of (25) expresses that b is in bet( X 1 , X 2 ) if it is between some element from X 1 and some element from X 2 . The third component is needed to correctly address the case where some of the attribute domains D 1 , . . . , D l are not orthogonal (in which case the second component is the empty set). In such a case, we will only find elements that are guaranteed to be between X 1 and X 2 if the attribute domains which are not orthogonal to the others are in some sense irrelevant. The following proposition shows the correctness of the definition of bet in [START_REF] Dubois | Similarity versus preference in fuzzy set-based logics[END_REF].

Proposition 3. Let X 1 , X 2 and Y be subsets of D 1 × • • • × D l . We have that Y ⊆ bet(X 1 , X 2 ) ⇒ bet reg(X 1 ), reg(Y ), reg(X 2 ) Example 13. Let X 1 = {(x, det, small) | x ∈ A 1 } and X 2 = {(x, det, large) | x ∈ A 1 }
, and assume that A 2 and A 3 are orthogonal (considering that the size of a house is irrelevant in deciding whether it is e.g. detached or not), while A 1 and A 2 are not. Noting that bet (det, small) , (det, large) = (det, small), (det, medium), (det, large)

we find bet( X 1 , X 2 ) = {(x, det, y) | x ∈ A 1 , y ∈ {small, medium, large}}.

Parallelism

The treatment of parallelism is largely analogous to the treatment of betweenness. If the attribute domains D 1 , . . . , D l are all orthogonal, the relation par can be defined for elements of

D 1 × • • • × D l as follows: par(a, b, c; d) iff (a = c ∧ b = d) ∨ (c = d) ∨ ∃ j. ∀i = j.(a i = b i ) ∧ (c i = d i ) ∧ par(a j , b j , c j ; d j ) (26)
As for betweenness, we find that a component-wise assessment of parallelism is not usually sufficient to provide guarantees To assess parallelism w.r.t. subsets X 1 , X 2 and X 3 of

D 1 × • • • × D l , we define: par(X 1 , X 2 , X 3 ) = Z 2 ∪ Z 3 ∪ d a ∈ X 1 , b ∈ X 2 , c ∈ X 3 , par(a, b, c; d) ∪ (d 1 , . . . , d i-1 , x, d i+1 , . . . , d l ) d ∈ par X ↓i 1 , X ↓i 2 , X ↓i 3 , 1 i l, x ∈ D i ∪ (d 1 , . . . , d i-1 , x, d i+1 , . . . , d l ) d ∈ par X ↓x 1 , X ↓y 2 , X ↓y 3 , 1 i l, x, y ∈ D i , D i orthogonal to D 1 , . . . , D i-1 , D i+1 , . . . , D l (27) with Z 2 = X 2 if X 1 ∩ X 3 is realizable X 1 ∩ X 2 ∩ X 3 otherwise Z 3 =        X 3 if X 1 and X 2 are realizable X 2 ∩ X 3 if X 1 is realizable but not X 2 X 1 ∩ X 3 if X 2 is realizable but not X 1 X 1 ∩ X 2 ∩ X 3 otherwise and for y ∈ D i and X ⊆ D 1 × • • • × D l we define (a 1 , . . . , a i-1 , a i+1 , . . . , a l ) ∈ X ↓y iff (a 1 , . . . , a i-1 , y, a i+1 , . . . , a l ) ∈ X
The set Z 2 corresponds to those elements that can be added to par( X 1 , X 2 , X 3 ) due to the trivial case where a = c ∧ b = d in [START_REF] Zadeh | A theory of approximate reasoning[END_REF], whereas Z 3 corresponds to the trivial case where c = d. In particular, if X 1 ∩ X 3 is realizable we know that for every point in X 2 we can find a point which belongs to both X 1 and X

3 , hence (X 1 ∩ X 3 , X 2 , X 1 ∩ X 3 , X 2 ) trivially defines two parallel directions, hence so does (X 1 , X 2 , X 3 , X 2 ). The definition of Z 3 is based on the intuition that (X 1 , X 2 , X 3 , X 3 )
trivially defines two parallel directions, but only if X 1 , X 2 and X 3 correspond to non-empty regions. As in the case of the set Z in the definition of bet, we need to take realizability into account. The third argument of the union in the right-hand side of ( 27) expresses the basic case: d is in par( X 1 , X 2 , X 3 ) if there are elements in X 1 , X 2 and X 3 such that the corresponding directions are parallel. The fourth argument allows us to ignore irrelevant attribute domains, similar as in the definition of bet in [START_REF] Dubois | Similarity versus preference in fuzzy set-based logics[END_REF]. For parallelism, however, there is another case where situations of parallelism in

D 1 × • • • × D i-1 × D i+1 × • • • × D l may be extended to D 1 × • • • × D l ,
which is covered by the last argument of the union. The central idea is that when D i is orthogonal to the other attribute domains, we can be more tolerant; note that

X ↓i 2 × X ↓i 3 ⊆ y∈D i X ↓y 2 × X ↓y 3 . Indeed, all
that is required is that we can extend vectors a, b, c and

d in D 1 × • • • × D i-1 × D i+1 × • • • × D l
, by choosing the same value x from D i to extend a and b and the same value y to extend c and d, without there being a requirement for x = y to hold.

On the other hand, regardless of the realizability of X 1 , X 2 and X 3 , we always define: ,b,c,d)

par(X 1 , X 2 , X 3 ) = d a ∈ X 1 , b ∈ X 2 , c ∈ X 3 , par(a
The correctness of the proposed definitions is demonstrated by the following propositions.

Proposition 4. Let X 1 , X 2 , X 3 and Y be subsets of D 1 × • • • × D l . We have that Y ⊆ par(X 1 , X 2 , X 3 ) ⇒ par reg(X 1 ), reg(X 2 ), reg(X 3 ); reg(Y ) Proposition 5. Let X 1 , X 2 , X 3 and Y be subsets of D 1 × • • • × D l . We have that par reg(X 1 ), reg(X 2 ), reg(X 3 ); reg(Y ) ⇒ Y ∩ par(X 1 , X 2 , X 3 ) = ∅

Comparative distance

The relations bet σ , bet σ , par τ and par τ behave in general similar to their counterparts bet, bet, par and par. The main exception is when σ = [λ, λ] or τ = [µ, µ] is a degenerate interval, i.e. a singleton, in which case bet σ and par τ hold as soon as these relations hold for each of the components, i.e. we have for each λ ∈ [0, 1] and

µ ∈ [0, +∞[ that bet [λ,λ] (a, b, c) iff ∀i.bet [λ,λ] (a i , b i , c i ) par [µ,µ] (a, b, c; d) iff ∀i.par [µ,µ] (a i , b i , c i ; d i )
provided that the attribute domains D 1 , . . . , D l are orthogonal; otherwise, we still cannot provide any guarantees on betweenness or parallelism beyond the trivial cases where a = b = c and a = b = c = d respectively. The underlying reason that the definition of bet σ becomes more tolerant when σ is a singleton is due to the fact that for points p = (p 1 , p 2 , . . . , p n ), q = (q 1 , q 2 , . . . , q n ), r = (r 1 , r 2 , . . . , r n ) in a Euclidean space, it holds that whenever we have q i = p i + λ(r i -p i ) for all i, we also have

--→ pq = λ • -→
pr; and similar for par τ .

If σ and τ are not singletons, bet σ and par τ are defined as:

bet σ (a, b, c) iff α 1 ∨ α 2 ∨ (a = b = c) ∨ ∃ j.(∀i = j.a i = b i = c i ) ∧ bet σ (a j , b j , c j ) par τ (a, b, c; d) iff β 1 ∨ β 2 ∨ (a = b) ∧ (c = d) ∨ ∃ j. ∀i = j.(a i = b i ) ∧ (c i = d i ) ∧ par τ (a j , b j , c j ; d j ) with α 1 ≡ a = b if 0 ∈ σ ⊥ otherwise α 2 ≡ b = c if 1 ∈ σ ⊥ otherwise β 1 ≡ (a = c) ∧ (b = d) if 1 ∈ τ ⊥ otherwise β 2 ≡ c = d if 0 ∈ τ ⊥ otherwise
and where again we assume that D 1 , . . . , D l are orthogonal. Note that bet σ and par τ are essentially defined as bet and par when σ and τ are not singletons, although some of the trivial cases only hold when they contain 0 or 1.

Moreover, in all cases bet σ and par τ are defined like bet and par:

bet σ (a, b, c) iff ∀ j.bet σ (a j , b j , c j ) par τ (a, b, c; d) iff ∀ j.par τ (a j , b j , c j ; d j )
Now we extend these relations to subsets of

D 1 × • • • × D l . Let X 1 and X 2 be subsets of D 1 × • • • × D l ; we define bet σ (X 1 , X 2 ) = Z 1 ∪ Z 2 ∪ b a ∈ X 1 , c ∈ X 2 , bet σ (a, b, c) ∪ (b 1 , . . . , b i-1 , x, b i+1 , . . . , b l ) b ∈ bet σ X ↓i 1 , X ↓i 2 , 1 i l, x ∈ D i ( 28
)
with

Z 1 = X 1 if X 2 is realizable and 0 ∈ σ X 1 ∩ X 2 otherwise Z 2 = X 2 if X 1 is realizable and 1 ∈ σ X 1 ∩ X 2 otherwise
The situation for par τ is mostly similar as for par:

par τ (X 1 , X 2 , X 3 ) = Z 2 ∪ Z 3 ∪ d a ∈ X 1 , b ∈ X 2 , c ∈ X 3 , par τ (a, b, c; d) ∪ (d 1 , . . . , d i-1 , x, d i+1 , . . . , d l ) d ∈ par τ X ↓i 1 , X ↓i 2 , X ↓i 3 , 1 i l, x ∈ D i ∪ (d 1 , . . . , d i-1 , x, d i+1 , . . . , d l ) d ∈ par τ X ↓x 1 , X ↓y 2 , X ↓y 3 , 1 i l, x, y ∈ D i , D i orthogonal to D 1 , . . . , D i-1 , D i+1 , . . . , D l (29) with Z 2 = X 2 if X 1 ∩ X 3 is realizable and 1 ∈ τ X 1 ∩ X 2 ∩ X 3 otherwise Z 3 =        X 3 if X 1 and X 2 are realizable and 0 ∈ τ or if X 1 ∩ X 2 is realizable X 2 ∩ X 3 if X 1 is realizable but not X 2 and 0 ∈ τ X 1 ∩ X 3 if X 2 is realizable but not X 1 and 0 ∈ τ X 1 ∩ X 2 ∩ X 3 otherwise Proposition 6. Let X 1 , X 2 , X 3 , and Y be subsets of D 1 × • • • × D l , let σ be a subset of [0, 1] and τ a subset of [0, +∞[. We have that Y ⊆ bet σ (X 1 , X 2 ) ⇒ bet σ reg(X 1 ), reg(Y ), reg(X 2 ) Y ⊆ par τ (X 1 , X 2 , X 3 ) ⇒ par τ reg(X 1 ), reg(X 2 ), reg(X 3 ); reg(Y ) Proposition 7. Let X 1 , X 2 , X 3 , and Y be subsets of D 1 × • • • × D l , let σ be a subset of [0, 1] and τ a subset of [0, +∞[. We have that bet σ reg(X 1 ), reg(Y ), reg(X 2 ) ⇒ Y ∩ bet σ (X 1 , X 2 ) = ∅ par τ reg(X 1 ), reg(X 2 ), reg(X 3 ); reg(Y ) ⇒ Y ∩ par τ (X 1 , X 2 , X 3 ) = ∅

Refining the rule base

From Postulates (bet1), (bet2), (par1) and (par2), we know that for all regions A 1 , A 2 , A 3 in B, it holds that:

m * bet σ (A 1 , A 2 ) ⊆ bet σ m * (A 1 ), m * (A 2 ) (30) m * par σ (A 1 , A 2 , A 3 ) ⊆ par σ m * (A 1 ), m * (A 2 ), m * (A 3 ) (31)
where m * is the point-wise extension of m as before, and

(σ ⊆ [0, 1], τ ⊆ [0, +∞[) bet σ (A 1 , A 2 ) = q ∃p ∈ A 1 , r ∈ A 2 , λ ∈ σ .bet(p, q, r) ∧ --→ pq = λ • -→ pr par τ (A 1 , A 2 , A 3 ) = {s | ∃p ∈ A 1 , q ∈ A 2 , r ∈ A 3 , λ ∈ τ . - → rs = λ • --→ pq}
In other words, we have that bet σ (A 1 , A 2 ) is the true set of points that are located between A 1 and A 2 with a relative distance from A 1 contained in σ , and similar for par τ (A 1 , A 2 , A 3 ). In particular, we have that bet

σ (A 1 , A 2 ) ⊆ bet σ (A 1 , A 2 ) (32) bet σ m * (A 1 ), m * (A 2 ) ⊆ bet σ m * (A 1 ), m * (A 2 ) (33) par τ (A 1 , A 2 , A 3 ) ⊆ par τ (A 1 , A 2 , A 3 ) (34) par τ m * (A 1 ), m * (A 2 ), m * (A 3 ) ⊆ par τ m * (A 1 ), m * (A 2 ), m * (A 3 ) (35)
Together with ( 30)- [START_REF] Dupin De Saint-Cyr | Belief extrapolation (or how to reason about observations and unpredicted change)[END_REF] and the monotonicity of f w.r.t. set inclusion, this yields

f bet σ (X 1 , X 2 ) ⊆ bet σ f (X 1 ), f (X 2 ) (36) f par τ (X 1 , X 2 , X 3 ) ⊆ par τ f (X 1 ), f (X 2 ), f (X 3 ) (37) for all X 1 , X 2 , X 3 ∈ 2 B .
Recall that the mapping f is unknown to us, and corresponds to the semantic counterpart of the 'ideal' rule base, containing all knowledge about m that can be encoded using the given vocabulary. However, given that f f R is assumed to hold (i.e. all knowledge encoded in R is correct), ( 36) and ( 37) allow us to refine the mapping f R , which is at our disposal, to the most conservative refinement f R that satisfies these two constraints, i.e. we define f R to be the largest fixpoint, w.r.t. the ordering defined in ( 14), of

f R {x} = f R {x} ∩ σ ⊆[0,1] bet σ f R (Y ), f R (Z ) x ∈ bet σ (Y , Z ) ∩ τ ⊆[0,+∞[ par τ f R (X), f R (Y ), f R (Z ) x ∈ par τ (X, Y , Z ) and f R (X) = x∈ X f R ({x}).
From the well-known Knaster-Tarski theorem [START_REF] Tarski | A lattice theoretical fixpoint theorem and its application[END_REF], we know that this largest fixpoint exists, and can be found in an iterative way as follows. Let f R

(0) = f R and f R (i+1) {x} = f R {x} ∩ σ ⊆[0,1] bet σ f R (i) (Y ), f R (i) (Z ) x∈ bet σ (Y , Z ) ∩ τ ⊆[0,+∞[ par τ f R (i) (X), f R (i) (Y ), f R (i) (Z ) x ∈ par τ (X, Y , Z ) (38)
and f R

(i+1) (X) = x∈ X f R (i+1) ({x}). It is clear that f R (i+1)
f R (i) , i.e. this definition allows us to repeatedly refine the initial function f R (0) . From the finiteness of the attribute domains B and C, it follows that this process must end, i.e. that there is

an i 0 ∈ N such that f R (i 0 +1) = f R (i 0 ) = f R . Proposition 8. Let f R ,
⊆ f R bet(X 1 , X 2 ) ⊆ bet f R (X 1 ), f R (X 2 ) ⊆ bet f R (X 1 ), f R (X 2 )
= bet (det, small, bas), (det, small, comf ) , (det, large, lux) = (det, x, y) | x ∈ {small, med, large}, y ∈ {bas, comf , lux} where X 1 and X 2 are as defined in Example 13. Furthermore, we also have

f R (villa, det, med) ⊆ f R (villa, det, med) = (det, med, x) | x ∈ A 4
Together we thus find f R (villa, det, med) ⊆ (det, med, bas), (det, med, comf ), (det, med, lux)

Syntactic characterization

In this section, we will analyse how conceptual relations behave at the syntactic level, i.e. how available background information on betweenness and parallelism of atoms can be lifted to relations between arbitrary propositional formulas. Together with the meta-principles (S), (I),(I'),(E),(E') and (D) introduced in Section 3.1, we will then be able to fully characterize a commonsense inference relation, and show its soundness and completeness w.r.t. the semantics from Section 5.

As elements from A can be identified with interpretations, any propositional formula α naturally corresponds to a set set(α) of elements S from A, which are the elements that correspond to the models of α, i.e. set(α) = {ω ∈ A | ω | A α}.

Conversely, every element a = (a 1 , . . . , a n ) from A corresponds to an interpretation, which can syntactically be characterized as a conjunction of atoms a 1 ∧ • • • ∧ a n ; let us write conj(a) for the conjunction corresponding to a ∈ A.

As input to the inference relation, in addition to the rule base R, we assume that a set of assertions Σ is given, which specifies the conceptual relations at the atom level. We define the closure Σ * of Σ to be the (infinite) set of all assertions that directly follow from assertions in Σ . In particular, we define Σ * as the smallest set of assertions which satisfies Σ ⊆ Σ * , and moreover for all a, b, c, and d:

bet σ (a, b, c) ∈ Σ * ⇒ bet 1-σ (c, b, a) ∈ Σ * bet σ (a, b, c) ∈ Σ * ⇒ bet 1-σ (c, b, a) ∈ Σ * bet σ (a, b, c) ∈ Σ * ∧ σ ⊆ σ ′ ⇒ bet σ ′ (c, b, a) ∈ Σ * bet σ (a, b, c) ∈ Σ * ∧ σ ⊆ σ ′ ⇒ bet σ ′ (c, b, a) ∈ Σ * par τ (a, b, c; d) ∈ Σ * ∧ τ ⊆ τ ′ ⇒ par τ ′ (a, b, c; d) ∈ Σ * par τ (a, b, c; d) ∈ Σ * ∧ τ ⊆ τ ′ ⇒ par τ ′ (a, b, c; d) ∈ Σ * bet σ (a, a, c) ∈ Σ * ⇒ bet σ (a, a, c) ∈ Σ * par τ (a, b, c; d) ∈ Σ * ⇒ par τ (a, b, c; d) ∈ Σ * 0 ∈ σ ⇒ bet σ (a, a, c) ∈ Σ * σ = ∅ ⇒ bet σ (a, a, a) ∈ Σ * 1 ∈ τ ⇒ par τ (a, b, a; b) ∈ Σ * 0 ∈ τ ⇒ par τ (a, b, c; c) ∈ Σ * τ = ∅ ⇒ par τ (a, a, b; b) ∈ Σ *
where we write 1 -σ for the set {1 -x | x ∈ σ }. Note that even though the set Σ * is infinite, it is straightforward to decide whether a given assertion such as bet σ (a, b, c) is in Σ * from the definition of Σ . In the following, we will use the assumption that the assertions in Σ are sound in the following sense:

for all labels a, b, c, d from the same attribute domain A i . In addition, the following assumptions are needed to show completeness, although they can be abandoned when completeness is not required (or feasible):

bet σ reg(a), reg(b), reg(c) ⇒ bet σ (a, b, c) ∈ Σ * (43) bet σ (a, b, c) ∈ Σ ⇒ bet σ reg(a), reg(b), reg(c) (44) par τ reg(a), reg(b), reg(c); reg(d) ⇒ par τ (a, b, c; d) ∈ Σ * (45) par τ (a, b, c; d) ∈ Σ ⇒ par τ reg(a), reg(b), reg(c); reg(d) (46)
In the following, we do not explicitly consider bet, par, bet and par, seeing these relations merely as abbreviations for bet [0,1] , par [0,+∞[ , bet [0,1] and par [0,+∞[ . Before we can characterize the conceptual relations, we need a syntactic counterpart for the notion of realizability, which played a key role in Section 5. As it turns out, at the syntactic level, realizability corresponds to a strong notion of consistency. More precisely, a formula α is called consistent if it has at least one model. Given a formula α, let us write domains(α) for the set of attribute domains to which α refers, i.e. for each atom a occurring in α, the attribute domain A i which contains a will be in domains(α). We then say that α is strongly consistent if there exists a consistent formula β such that β | α and all attribute domains in domains(α) are orthogonal to each other. The correspondence with realizability is demonstrated by the following lemma.

Lemma 1. It holds that a formula α is strongly consistent iff set(α) is realizable.

To formalize what can be inferred from Σ , we again follow a normative approach. In particular, we consider that an expression of the form α → β ✶ σ γ is supported by Σ if it can be derived using the following rules.

(bet 1 ) If bet σ (a, x, b) ∈ Σ then Σ ⊢ x → a ✶ σ b. (bet 2 ) If α 2 | A α 1 , β 1 | A β 2 , γ 1 | A γ 2 and σ 1 ⊆ σ 2 , then whenever we have Σ ⊢ α 1 → β 1 ✶ σ 1 γ 1 we also have Σ ⊢ α 2 → β 2 ✶ σ 2 γ 2 . (bet 3 ) If Σ ⊢ α → β ✶ σ γ then Σ ⊢ α → γ ✶ (1-σ ) β. (bet 4 ) If β is strongly consistent and 0 ∈ σ , we have Σ ⊢ α → α ✶ σ β. (bet 5 ) It always 7 holds that Σ ⊢ α → α ✶ σ α. (bet 6 ) If Σ ⊢ α 1 → β 1 ✶ σ γ 1 and Σ ⊢ α 2 → β 2 ✶ σ γ 2 then Σ ⊢ α 1 ∨ α 2 → (β 1 ∨ β 2 ) ✶ σ (γ 1 ∨ γ 2 ). (bet 7 ) If Σ ⊢ α → β ✶ σ γ , δ is strongly consistent and the attribute domains in domains(α) ∪ domains(β) ∪ domains(γ ) are orthogonal to those in domains(δ), then Σ ⊢ α ∧ δ → (β ∧ δ) ✶ σ (γ ∧ δ). (bet 8 ) If Σ ⊢ α 1 → β 1 ✶ [λ,λ] γ 1 , Σ ⊢ α 2 → β 2 ✶ [λ,
λ] γ 2 and the attribute domains in domains(α 1 ) ∪ domains(β 1 ) ∪ domains(γ 1 ) are orthogonal to those in domains(α 2 )

∪ domains(β 2 ) ∪ domains(γ 2 ), then Σ ⊢ α 1 ∧ α 2 → (β 1 ∧ β 2 ) ✶ [λ,λ] (γ 1 ∧ γ 2 ). (bet 9 ) It holds that Σ ⊢ ⊥ → β ✶ σ γ ,
where we write 1 -σ as a shorthand for {1λ | λ ∈ σ }. The soundness and completeness of these inference rules w.r.t. the semantics from Section 5 is shown by the following proposition. Proposition 9. Assume that Σ satisfies [START_REF] Kuipers | Qualitative simulation[END_REF] and [START_REF] Aisbett | A general formulation of conceptual spaces as a meso level representation[END_REF]. It holds that Σ ⊢ α → β ✶ σ γ can be derived from the inference rules

(bet 1 )-(bet 9 ) iff set(α) ⊆ bet σ (set(β), set(γ )).
If Σ only satisfies [START_REF] Kuipers | Qualitative simulation[END_REF] we still have that whenever Σ ⊢ α → β ✶ σ γ can be derived, we also have set(α) ⊆ bet σ (set(β), set(γ )), i.e. inference is still sound. Conversely, to show that Σ ⊢ α → β ✶ σ γ can be derived whenever set(α) ⊆ bet σ (set(β), set(γ )) holds, we only need [START_REF] Aisbett | A general formulation of conceptual spaces as a meso level representation[END_REF].

Example 15.

Consider the rules about wines from Example 10, and assume that the attribute domains are given by A 1 = {beaujolais, bardolino, valpolicalla, . . .} A 2 = {inexpensive, mid-range, above-average, high-end} A 3 = {low-tannins, mid-tannins, high-tannins} A 4 = {light-body, medium-body, full-body} A 5 = {light-red, medium-red, dark-red, opaque}

The assertions in Σ about A 1 are assumed to have been obtained using data-driven techniques, as was explained in Section 4.2. The assertions about A 2 , A 3 , A 4 and A 5 are obtained from the natural ranking of the labels, by assuming that they are all represented in a uni-dimensional domain. Recall that in uni-dimensional domains, the relations bet σ and bet σ coincide, as do par σ and par σ . In the following, we will assume that A 1 and A 2 are orthogonal, and that A 3 and A 4 are orthogonal.

Using (bet 1 ), we find:

Σ ⊢ barbera → chianti ✶ [0,1] merlot (47)
Σ ⊢ medium-body → light-body ✶ [0,1] full-body [START_REF] Bayoudh | Evaluation of analogical proportions through Kolmogorov complexity[END_REF] and using (bet 7 ):

Σ ⊢ (mid-tan ∧ med-body) → (mid-tan ∧ light-body) ✶ [0,1] (mid-tan ∧ full-body) (49)
Next, we consider formulas of the form β ✶ σ γ → α

(bet 1 ) We always have Σ ⊢ a ✶ σ b → {x | bet σ (a, x, b) ∈ Σ * }. (bet 2 ) If α 1 | A α 2 , β 2 | A β 1 , γ 2 | A γ 1 and σ 2 ⊆ σ 1 , then whenever we have Σ ⊢ β 1 ✶ σ 1 γ 1 → α 1 we also have Σ ⊢ β 2 ✶ σ 2 γ 2 → α 2 . (bet 3 ) If Σ ⊢ β ✶ σ γ → α then Σ ⊢ γ ✶ 1-σ β → α. (bet 4 ) If Σ ⊢ β 1 ✶ σ γ → α 1 , Σ ⊢ β 2 ✶ σ γ → α 2 then Σ ⊢ (β 1 ∨ β 2 ) ✶ σ γ → α 1 ∨ α 2 . (bet 5 ) If Σ ⊢ β 1 ✶ σ γ 1 → α 1 and Σ ⊢ β 2 ✶ σ γ 2 → α 2 then Σ ⊢ (β 1 ∧ β 2 ) ✶ σ (γ 1 ∧ γ 2 ) → α 1 ∧ α 2 . (bet 6 ) It holds that Σ ⊢ ⊥ ✶ σ γ → α.
Again we can show soundness and completeness.

Proposition 10. Assume that Σ satisfies and [START_REF]Formalizing conceptual spaces[END_REF]. It holds that Σ ⊢ β ✶ σ γ → α can be derived from the inference rules

(bet 1 )-(bet 6 ) iff bet σ (set(β), set(γ )) ⊆ set(α).
Example 16. Continuing the wine example, we obtain from (bet 1 ) that

Σ ⊢ mid-tannin ✶ [0,1] low-tannin → low-tannin ∨ mid-tannin (50) Σ ⊢ mid-tannin ✶ [0,1] mid-tannin → mid-tannin (51) Σ ⊢ medium-body ✶ [0,1] medium-body → medium-body (52)
Combining ( 50) and ( 51) using (bet 3 ) and (bet 4 ), we find

Σ ⊢ (low-tannin ∨ mid-tannin) ✶ [0,1] low-tannin → (low-tannin ∨ mid-tannin) (53)
Combining ( 52) and ( 53), we find

Σ ⊢ (low-tan ∨ mid-tan) ∧ med-bod ✶ [0,1] (low-tan ∧ med-bod) → (low-tan ∨ mid-tan) ∧ med-bod (54)
In a similar way, we can also consider expressions of the form δ → γ ✄ τ α, β :

(par 1 ) If par τ (a, b, c; d) ∈ Σ then Σ ⊢ d → c ✄ τ a, b . (par 2 ) If α 1 | A α 2 , β 1 | A β 2 , γ 1 | A γ 2 , δ 2 | A δ 1 and τ 1 ⊆ τ 2 , then whenever we have Σ ⊢ δ 1 → γ 1 ✄ τ 1 α 1 , β 1 we also have Σ ⊢ δ 2 → γ 2 ✄ τ 2 α 2 , β 2 . ( par
3 ) If α is strongly consistent and 1 ∈ τ , we always have Σ ⊢ β → α ✄ τ α, β . (par 4 ) We always8 have that Σ ⊢ α → α ✄ τ α, α . (par 5 ) If α is strongly consistent, we always have Σ ⊢ β → β ✄ τ α, α . (par 6 ) If α and β are strongly consistent and 0 ∈ τ , we always have Σ ⊢ γ → γ ✄ τ α, β . (par 7 ) If β is strongly consistent and 0 ∈ τ , we always have

Σ ⊢ α → α ✄ τ α, β . (par 8 ) If α is strongly consistent and 0 ∈ τ , we always have Σ ⊢ β → β ✄ τ α, β . (par 9 ) If Σ ⊢ δ 1 → γ 1 ✄ τ α 1 , β 1 and Σ ⊢ δ 2 → γ 2 ✄ τ α 2 , β 2 then Σ ⊢ δ 1 ∨ δ 2 → (γ 1 ∨ γ 2 ) ✄ τ α 1 ∨ α 2 , β 1 ∨ β 2 . (par 10 ) If Σ ⊢ δ → γ ✄ τ α, β ,
φ and ψ are strongly consistent, and the attribute domains in domains(α) ∪ domains(β) ∪ domains(γ )∪domains(δ) are orthogonal to those in domains(φ)∪domains(ψ

), then Σ ⊢ δ ∧ψ → γ ∧ ψ ✄ τ α ∧ φ, β ∧ φ . (par 11 ) If Σ ⊢ δ 1 → γ 1 ✄ [λ,λ] α 1 , β 1 , Σ ⊢ δ 2 → γ 2 ✄ [λ,λ] α 2 , β 2 ,

and the attribute domains in domains

(α 1 ) ∪ domains(β 1 ) ∪ domains(γ 1 ) ∪ domains(δ 1 ) are orthogonal to those in domains(α 2 ) ∪ domains(β 2 ) ∪ domains(γ 2 ) ∪ domains(δ 2 ), then Σ ⊢ δ 1 ∧ δ 2 → (γ 1 ∧ γ 2 ) ✄ [λ,λ] α 1 ∧ α 2 , β 1 ∧ β 2 . (par 12 ) It holds that Σ ⊢ ⊥ → γ ✄ τ α, β .
Proposition 11. Assume that Σ satisfies (41) and (45). It holds that Σ ⊢ δ → γ ✄ τ α, β can be derived from the inference rules (par 1 )-(par 12 ) iff set(δ) ⊆ par τ (set(α), set(β), set(γ )).

Σ ⊢ (high-tan ∧ med-bod) → (mid-tan ∧ med-bod) ✄ [0,+∞[ (low-tan ∧ med-bod), (mid-tan ∧ med-bod) (58) Σ ⊢ (mid-tan ∧ full-bod) → (mid-tan ∧ med-bod) ✄ [0,+∞[ (low-tan ∧ light-bod), (low-tan ∧ med-bod) (59)
Finally, we specify how formulas of the form γ ✄ τ α, β → δ can be derived:

(par 1 ) We always have Σ ⊢ c ✄ τ a, b → {d | par τ (a, b, c; d) ∈ Σ * }. (par 2 ) If α 2 | A α 1 , β 2 | A β 1 , γ 2 | A γ 1 , δ 1 | A δ 2 and τ 2 ⊆ τ 1 , then whenever we have Σ ⊢ γ 1 ✄ τ 1 α 1 , β 1 → δ 1 we also have Σ ⊢ γ 2 ✄ τ 2 α 2 , β 2 → δ 2 . (par 3 ) If Σ ⊢ γ ✄ τ α 1 , β → δ 1 and Σ ⊢ γ ✄ τ α 2 , β → δ 2 then Σ ⊢ γ ✄ τ α 1 ∨ α 2 , β → δ 1 ∨ δ 2 . (par 4 ) If Σ ⊢ γ ✄ τ α, β 1 → δ 1 and Σ ⊢ γ ✄ τ α, β 2 → δ 2 then Σ ⊢ γ ✄ τ α, β 1 ∨ β 2 → δ 1 ∨ δ 2 . (par 5 ) If Σ ⊢ γ 1 ✄ τ α, β → δ 1 and Σ ⊢ γ 2 ✄ τ α, β → δ 2 then Σ ⊢ (γ 1 ∨ γ 2 ) ✄ τ α, β → δ 1 ∨ δ 2 . (par 6 ) If Σ ⊢ γ 1 ✄ τ α 1 , β 1 → δ 1 , Σ ⊢ γ 2 ✄ τ α 2 , β 2 → δ 2 then Σ ⊢ (γ 1 ∧ γ 2 ) ✄ τ α 1 ∧ α 2 , β 1 ∧ β 2 → δ 1 ∧ δ 2 . (par 7 ) It holds that Σ ⊢ ⊥ ✄ τ α, β → δ. (par 8 ) It holds that Σ ⊢ γ ✄ τ ⊥, β → δ. (par 9 ) It holds that Σ ⊢ γ ✄ τ α, ⊥ → δ.
Proposition 12. Assume that Σ satisfies (42) and (46). It holds that Σ ⊢ γ ✄ τ α, β → δ can be derived from the inference rules

(par 1 )-(par 9 ) iff par τ (set(α), set(β), set(γ )) ⊆ set(α).
Example 18. Using (par 1 ), we find

Σ ⊢ mid-tan ✄ [0,+∞[ low-tan, high-tan → (mid-tan ∨ high-tan) Σ ⊢ high-tan ✄ [0,+∞[ low-tan, high-tan → high-tan
Combining these two assertions using (par 5 ) this yields

Σ ⊢ (mid-tan ∨ high-tan) ✄ [0,+∞[ low-tan, high-tan → (mid-tan ∨ high-tan) (60)
In entirely the same fashion, we arrive at

Σ ⊢ (mid-tan ∨ high-tan) ✄ [0,+∞[ mid-tan, high-tan → (mid-tan ∨ high-tan) (61)
Combining (60) and (61) using (par 3 ) gives us

Σ ⊢ (mid-tan ∨ high-tan) ✄ [0,+∞[ low-tan ∨ mid-tan, high-tan → (mid-tan ∨ high-tan) (62)
Furthermore, we find using (par 1 ):

Σ ⊢ med-bod ✄ [0,+∞[ med-bod, full-bod → (med-bod ∨ full-bod) Σ ⊢ full-bod ✄ [0,+∞[ med-bod, full-bod → full-bod
which we can combine using (par 5 ) to obtain:

Σ ⊢ (med-bod ∨ full-bod) ✄ [0,+∞[ med-bod, full-bod → (med-bod ∨ full-bod) (63)
We can then combine (62) and ( 63) using (par 6 ) to conclude

Σ ⊢ (mt ∨ ht) ∧ (mb ∨ fb) ✄ [0,+∞[ (lt ∨ mt) ∧ mb , (ht ∧ fb) → (mt ∨ ht) ∧ (mb ∨ fb) (64)
where we have further abbreviated the labels. Using (par 1 ) we also find

Σ ⊢ dark-red ✄ [0,+∞[ light-red, medium-red → (dark-red ∨ opaque) Σ ⊢ opaque ✄ [0,+∞[ light-red, medium-red → opaque Σ ⊢ dark-red ✄ [0,+∞[ medium-red, dark-red → (dark-red ∨ opaque) Σ ⊢ opaque ✄ [0,+∞[ medium-red, dark-red → ∨opaque Σ ⊢ dark-red ✄ [0,+∞[ medium-red, opaque → (dark-red ∨ opaque) Σ ⊢ opaque ✄ [0,+∞[ medium-red, opaque → opaque Applying (par 5 ) this leads to Σ ⊢ (dark-red ∨ op) ✄ [0,+∞[ light-red, med -red → (dark-red ∨ op) (65) Σ ⊢ (dark-red ∨ op) ✄ [0,+∞[ med-red, dark-red → (dark-red ∨ op) (66) Σ ⊢ (dark-red ∨ op) ✄ [0,+∞[ med-red, op → (dark-red ∨ op) (67)
and after applying (par 4 ), we also find

Σ ⊢ (dark-red ∨ opaque) ✄ [0,+∞[ medium-red, (dark-red ∨ opaque) → (dark-red ∨ opaque) (68)
We are now ready to show the soundness and completeness of the inference rules proposed in Section w.r.t. the semantics introduced in Section 5. 47), ( 54), ( 69) and ( 70 (R, Σ) ⊢ bandol → dark-red ∨ opaque again using (D). Despite that nothing could be concluded about bandol wine using classical deduction, using a combination of interpolative and extrapolative reasoning, we have found that its colour is either dark-red or opaque.

(R, Σ) ⊢ chianti → low-tan ∧ med-body (69) (R, Σ) ⊢ merlot → (low-tan ∨ mid-tan) ∧ med-body (70) (R, Σ) ⊢ barolo → high-tan ∧ full-body (71) (R, Σ) ⊢ zinfandel → (mid-tan ∨ high-tan) ∧ (med-body ∨ full-body) (72) (R, Σ) ⊢ low-tan ∧ light-body → light-red (73) (R, Σ) ⊢ low-tan ∧ med-body → med-red (74) (R, Σ) ⊢ mid-tan ∧ med-body → dark-red ∨ opaque (75) (R, Σ) ⊢ high-tan ∧ full-body → opaque (76) Combining (

Complexity and implementation

In this section, we first show that interpolative and extrapolative reasoning is PSPACE-hard in general. We then show in Section 7.4 that the complexity crucially depends on the number of attribute domains. In particular, we show that implementations in polynomial time are possible when the number of attribute domains is small enough to be treated as a constant (without placing any bounds on the number of attributes or the number of rules). From this result, it also follows that the inference problem considered in this paper is decidable in EXPTIME. However, whether this problem is also in PSPACE remains currently open.

Hardness

We prove that interpolative and extrapolative reasoning are PSPACE-hard, by showing a reduction from the dominance problem for CP-nets [START_REF] Boutilier | CP-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF]. We present two such reductions, one which is only based on interpolative reasoning and one which is only based on extrapolative reasoning.

Our terminology and notations are based on the presentation of CP-nets in [START_REF] Goldsmith | The computational complexity of dominance and consistency in CP-nets[END_REF], where a generalization of binary CP-nets is considered. The basic building blocks are conditional preference rules, which are expressions of the form p : x i > ¬x i (or p : ¬x i > x i ) with p a propositional formula over a set of atoms V = {x 1 , . . . , x n } and x i an atom from V . The intuitive meaning is that in situations where p holds, having x i true is preferred to having x i false. A (binary) GCP-net (generalized ceteris paribus net) over V is a set of such conditional preference rules. An outcome is an n-tuple (I(x 1 ), . . . , I(x n )) where I maps each variable to a value from {true, false}, i.e. an outcome corresponds to a propositional interpretation. For the ease of presentation, we will identify an outcome with its corresponding mapping I . Let I and J be two outcomes, which differ only in the value of one variable x i , such that I(x i ) = true and J (x i ) = false. If a GCP-net N contains a rule p : x i > ¬x i (resp. p : ¬x i > x i ) such that the propositional formula p is satisfied by both I and J , we say that N sanctions an improving flip from J to I (resp. from I to J ). Finally, we say that I dominates J , given N, if there is a sequence J = J 0 , J 1 , . . . , J m = I such that N sanctions an improving flip from J i to J i+1 for each i in {0, . . . , m -1}. The problem of deciding, given two outcomes I and J , whether I dominates J is PSPACE-complete [START_REF] Goldsmith | The computational complexity of dominance and consistency in CP-nets[END_REF].

Reduction to interpolative reasoning

Given a GCP-net N and two outcomes I and J we now construct a rule base R and a set of assertions Σ such that I dominates J iff a particular rule can be derived from R using interpolative reasoning. We consider an attribute domain Y = {y 0 , y 1 , y 2 }, and one additional attribute domain X i for each variable x i ∈ V , which is defined as

X i = {x i , x i } ∪ x p i (p: x i > ¬x i ) ∈ N ∪ x i p (p: ¬x i > x i ) ∈ N
The set of rules R is obtained by adding for each conditional preference rule of the form p:

x i > ¬x i in N the rule p ∧ x p i → y 2 (82)
and for each conditional preference rule of the form p : ¬x i > x i , we add to R the rule

p ∧ x i p → y 2 (83)
Finally, we also add the rule

x i J (x i ) = true, 1 i n ∧ x i J (x i ) = false, 1 i n → y 1 ( 84
)
The underlying idea is combine rules of the form (84) with rules of the form (82) or (83) using inference rule (I') to simulate the idea of an improving flip. The antecedents of each of the newly generated rules will correspond to outcomes (where a conjunct x i appears if x i is true in the outcome, and a conjunct x i appears otherwise). To this end, for each conditional preference rule of the form p: x i > ¬x i we add the assertion bet [0,1] (x i , x i , x p i ) to Σ and for each conditional preference rule of the form p: ¬x i > x i we add the assertion bet [0,1] (x i , x i , x i p ). We also add the assertion bet [0,1] (y 0 , y 1 , y 2 ).

Proposition 14. Let I , J , N, R, and Σ be as above. It holds that I dominates J , given N, iff (R, Σ) ⊢

x i I(x i ) = true, 1 i n ∧ x i I(x i ) = false, 1 i n → y 1 ∨ y 2
(85)

Reduction to extrapolative reasoning

We now show that the idea of improving flips can also be simulated using extrapolative reasoning, i.e. using assertions about the relations par and par in Σ . With each variable x i we now associate an attribute domain X i = {x i , x i , x ′ i , x ′ i }. We consider one additional attribute domain Y = {y 0 , y 1 , y 2 , y -, y + } whose elements will again appear in the consequent of rules. Intuitively, y 1 is the degree to which outcome J is preferred, y 0 is a lower degree of preference and y 2 is a higher degree of preference. Furthermore, y -represents a lower degree of preference than y + , but the relation between y -and y + on the one hand, and y 0 , y 1 and y 2 on the other hand will remain unspecified. For each conditional preference rule p : x i > ¬x i in N, we add the following two rules to

R p ∧ x ′ i → y + p ∧ x i → y -
The idea here is to indicate that the direction from having x i false to having x i true is towards more preferred outcomes when p is true. By using the attributes x ′ i and x i , rather than x i and x we can talk about the effect of changing the value of x i without the need to specify to what degree p ∧ x i and p ∧ x are preferred. Similarly, for each preference rule of the form p : ¬x i > x i , we add

p ∧ x i → y + p ∧ x ′ i → y -
Finally, we add the rule

x i J (x i ) = true, 1 i n ∧ x J (x i ) = false, 1 i n → y 1
For each i, we add the assertions (R, Σ) ⊢

x i I(x i ) = true, 1 i n ∧ x I(x i ) = false, 1 i n → y 1 ∨ y 2
Corollary 1. The problem of deciding whether (R, Σ) ⊢ α → β is PSPACE-hard, even if either all betweenness information in Σ is trivial, or all information about parallelism in Σ is trivial.

Implementation

In propositional logic, the number of possible interpretations is exponential in the number of atoms. In the present setting, on the other hand, the number of interpretations strongly depends on the number of attribute domains. If the number of attribute domains is small compared to the total number of atoms, the number of interpretations is essentially polynomial. For example, if there are only two attribute domains A 1 and A 2 , each of which contains n 2 atoms, then there are ( n 2 2 interpretations. In such cases, it makes sense to rely on implementation methods that operate at the semantic level, even if that requires an enumeration of all interpretations.

Consider a rule base R, where the antecedents of rules are built from the atoms in B 1 , . . . , B s and the consequents are built from C 1 , . . . , C k . From Proposition 13, we know that we can fully characterize interpolation and extrapolation on R by specifying the value of f R for each element (x 1 , . . . , [START_REF] Forbus | Qualitative process theory[END_REF], we know that the function f R can be obtained in an iterative fashion, although the formulation in [START_REF] Forbus | Qualitative process theory[END_REF] cannot be used directly, as it involves intersections that range over arbitrary subsets of interpretations (of which there are at least exponentially many) and arbitrary subsets of [0, 1] and [0, +∞[. The following proposition suggests a way to evaluate the right-hand side of [START_REF] Forbus | Qualitative process theory[END_REF] in practice.

x s ) of B = B 1 × • • • × B s . Moreover, from
Proposition 16. Let x = (x 1 , . . . , x s ). It holds that f R (i+1) {x} = f (i) R {x} ∩ bet σ f R (i) set(α) , f R (i) set(γ ) c 1 ∨ c 2 ∩ par τ f R (i) set(α) , f R (i) set(β) , f R (i) set(γ ) c 3 ∨ c 4 ( 86
)
where

c 1 iff α = x i 1 ∧ • • • ∧ x i j-1 ∧ a i j ∧ x i j+1 ∧ • • • ∧ x i r and γ = x i 1 ∧ • • • ∧ x i j-1 ∧ c i j ∧ x i j+1 ∧ • • • ∧ x i r and Σ ⊢ x i j → a i j ✶ σ c i j with B i 1 , . . . , B i r all orthogonal c 2 iff α = a i 1 ∧ • • • ∧ a i r and γ = c i 1 ∧ • • • ∧ c i r and ∃λ ∈ [0, 1].∀ j ∈ {1, . . . , r}.Σ ⊢ x i j → a i j ✶ [λ,λ] c i j with B i 1 , . . . , B i r all orthogonal c 3 iff α = y i 1 ∧ • • • ∧ y i j-1 ∧ a i j y i j+1 ∧ • • • ∧ y i r and β = y i 1 ∧ • • • ∧ y j-1 ∧ b i j ∧ y i j+1 ∧ • • • ∧ y i r and γ = x i 1 ∧ • • • ∧ x i j-1 ∧ c i j ∧ x i j+1 • • • ∧ x i r and Σ ⊢ x i j → c i j ✄ τ a i j , b j with B i 1 , . . . , B i r all orthogonal c 4 iff α = a i 1 ∧ • • • ∧ a i r and β = b i 1 ∧ • • • ∧ b i r and γ = c i 1 ∧ • • • ∧ c i r and ∃µ ∈ [0, +∞[.∀ j ∈ {1, . . . , r}.Σ ⊢ x i j → c i j ✄ [µ,µ] a i j , b i j with B i 1 , . .

. , B i r all orthogonal

Note in particular how Proposition 16 allows us to replace the range of the intersection over arbitrary subsets of B to a range over conjunctions α, β and γ , of which there are polynomially many if the number of attribute domains is treated as a constant. Moreover, note how for each choice of these conjunctions, there is only one minimal choice for σ or τ , which can easily be found from Σ . This leads to the following procedure to characterize the function f R at the semantic level:

repeat the following until f R 1) , starting with i = 1, for each x ∈ B:

(i) = f R (i-
1. set S ← f R (i-1) ({x});

2. for each non-empty subset {i 1 , . . . , i r } such that B i 1 , . . . , B i r are all orthogonal:

(a) for each j ∈ {1, . . . , r} and for each a i j and c i j in B i j such that bet σ (a i j , x i j , c i j ) ∈ Σ for some σ ⊆ [0, 1]: i. set α

← x i 1 ∧ • • • ∧ x i j-1 ∧ a i j ∧ x i j+1 ∧ • • • ∧ x i r ii. set γ ← x i 1 ∧ • • • ∧ x i j-1 ∧ c i j ∧ x i j+1 ∧ • • • ∧ x i r iii. set S ← S ∩ bet σ ( f R (i-1) (set(α)), f R (i-1) (set(γ )))
(b) for each λ ∈ [0, 1] for which Σ contains relations of the form bet [λ,λ] , and each a i 1 , . . . , a i r , c i 1 , . . . , c i r such that for each j it holds that bet [λ,λ] (a i j , 1) (set(γ )));

x i j , c i j ) ∈ Σ or bet [λ,λ] (c i j , x i j , a i j ) ∈ Σ or a i j = x i j = c i j : i. set α ← a i 1 ∧ • • • ∧ a i r ; ii. set γ ← c i 1 ∧ • • • ∧ c i r ; iii. set S ← S ∩ bet [λ,λ] ( f R (i-1) (set(α)), f R (i-
(c) for each j ∈ {1, . . . , r}, for each y i 1 , . . . , y i j-1 , y i j+1 , . . . , y i r and for each a i j , b i j and c i j in B i j such that par τ (a i j , b i j , c i j ;

x i j ) ∈ Σ for some τ ⊆ [0, +∞[: i. set α ← y i 1 ∧ • • • ∧ y i j-1 ∧ a i j ∧ y i j+1 ∧ • • • ∧ y i r ; ii. set β ← y i 1 ∧ • • • ∧ y i j-1 ∧ b i j ∧ y i j+1 ∧ • • • ∧ y i r ; iii. set γ ← x i 1 ∧ • • • ∧ x i j-1 ∧ c i j ∧ x i j+1 ∧ • • • ∧ x i r ; iv. set S ← S ∩ par τ ( f R (i-1) (set(α)), f R (i-1) (set(β)), f R (i-
: i. set α ← a i 1 ∧ • • • ∧ a i r ; ii. set α ← b i 1 ∧ • • • ∧ b i r ; iii. set γ ← c i 1 ∧ • • • ∧ c i r ; iv. set S ← S ∩ par [µ,µ] ( f R (i-1) (set(α)), f R (i-1) (set(β)), f R (i-1) (set(γ ))); 3. set f R (i) ({x}) ← S.
Note that in step 2(a), it suffices to check whether bet σ (a i j , x i j , c i j ) ∈ Σ to verify Σ ⊢ x i j → a i j ✶ σ c i j , as all other cases where Σ ⊢ x i j → a i j ✶ σ c i j holds are covered in one way or another. Indeed, when bet σ ′ (a i j , x i j , c i j ) ∈ Σ , for some σ ′ ⊂ σ , we have 1) set(γ ) so we do not need to consider bet σ if we already consider bet σ ′ . The case where bet σ (c i j , x i j , a i j ) ∈ Σ is handled by swapping the definitions of α and γ . Finally, the cases where x i j = a i j or x i j = c i j do not need to be considered because then x ∈ set(α) and 0 ∈ σ , x ∈ set(γ ) and 1 ∈ σ or x i j = a i j = c i j ; in each of these cases we have

bet σ ′ f R (i-1) set(α) , f R (i-1) set(γ ) ⊆ bet σ f R (i-1) set(α) , f R (i-
bet σ ( f R (i-1) (set(α)), f R (i-1) (set(γ ⊆ f (i-1) ({x i }). Similar considerations apply to (b)-(d).
It is clear that each of the steps (a)-(d) is polynomial in the size of B, as is the number of arguments x for which these steps have to be completed. Finally, after each iteration, there is at least one element x from B for which

f (i) R ({x}) ⊂ f (i-1) R ({x}), unless f (i) R = f R
after which we can stop. This means that the total number of iterations is upper bounded by B × C, and is in particular polynomial in the size of A. This means that the above procedure runs in polynomial time if the number of attribute domains n is small enough to be treated as a constant. In other words, interpolative and extrapolative reasoning is decidable in exponential time, and is polynomial in data complexity. The restriction to have a relatively small number of attribute domains is a natural one in many application contexts. For example, interpolation is often applied to sets of parallel if-then rules, in which case the antecedent of every rule is built from the same attribute domains, and the consequent is a single atom, taken from a fixed attribute domain. In such a case it is not common to have more than a few attribute domains. As another example, consider a rule base R = R 1 ∪ R 2 , such that the antecedents of rules in R 1 are built from the attribute domains B 1 , . . . , B k , the consequents of rules in R 1 and antecedents of rules in R 2 are built from the attribute domains C 1 , . . . , C s , and the consequents of rules in R 2 are built from the attribute domains D 1 , . . . , D l , such that {B 1 , . . . , B k } ∩ {D 1 , . . . , D l } = ∅. In many situations, refining R 1 and R 2 separately would be equivalent to refining R as a whole. The following counterexample, however, shows that this is not the case in general.

Example 20. Let

R = R 1 ∪ R 2 with R 1 = {a 1 → a 2 , c 1 → c 2 } and R 2 = {a 2 → a 3 , c 2 → c 3 }, where the attribute domains are A 1 = {a 1 , b 1 , c 1 , d 1 }, A 2 = {a 2 , b 2 , c 2 ,

Discussion

As explained in Section interpolative and extrapolative inference should provide sound conclusions as long as the rule base can be seen as the approximation of a mapping m which is linear, or in the case of interpolation, monotonic. In practice, however, this assumption may not be valid, in which case inconsistencies can be introduced by our method. In such cases, interpolative and extrapolative reasoning could still prove useful, although it should be applied more cautiously.

Relaxing the linearity assumption

mid-day → heavy-traffic

which is in conflict with (88). This can be explained due to a failure of the monotonicity assumption. In the case of (87)-(89) the underlying mapping is not even deterministic, in the sense that the exact amount of traffic at e.g. 9 am may vary from day to day (even if we assume that the rule base talks about weekdays in a specific city). Nonetheless, even for rules where the linearity assumption fails, interpolation may still be useful. For instance, suppose we introduce the labels mid-morning and mid-afternoon, which are between morning and mid-day, and between mid-day and evening respectively. From (87) and (88) we may derive mid-morning → moderate-traffic ∨ heavy-traffic Indeed, while the mapping underlying the rule base may, in principle, be arbitrary, it seems natural to assume that more regular mappings would be more likely, i.e. we could make the assumption that any completion of the knowledge base should not introduce additional irregularities. In particular, by identifying irregularities with violations of the monotonicity assumption, this leads to the assumption that the conceptual space C 1 corresponding with the antecedent of the rules can be partitioned in a minimal number of segments, such that the mapping is monotonic over these segments. In the traffic example, we would thus assume that the amount of traffic is monotonically decreasing throughout the morning and monotonically increasing throughout the afternoon. While such conclusions would not be valid in general, they are reasonable to make in absence of any other information. Depending on how the rule base (87)-( 89) was obtained, we may also argue that the absence of a rule for mid-morning suggests that this case is not special, i.e. that those cases which are irregular in some sense would be more likely to be contained in the rule base.

To avoid inconsistencies, the above view suggests that from a rule base R we should try to identify subsets R 1 , . . . , R k of rules, such that no inconsistencies arise as long as interpolation is applied to two rules from the same set R i . To be compatible with the above view, we should moreover insist that when α

→ α 1 ✶ α 2 , (α 1 → β 1 ) ∈ R i , (α 2 → β 2 ) ∈ R i and
(α → β) ∈ R, then we should have that (α → β) ∈ R i . In other words, the sub-bases R i should contain all rules that apply to a given (convex) segment of the conceptual space C 1 . In this way, we can ensure that when a new rule α * → β * is derived by interpolation from a sub-base R i , the rules in R i are indeed the most relevant ones, i.e. that they are the ones whose antecedent is closest to α * in some sense. In a similar, but slightly less cautious fashion, we may assume that the mapping underlying the rule base R is piecewise linear, and apply extrapolation locally to the sub-bases R 1 , . . . , R k .

Restricting to the most salient properties

Another reason why inconsistencies may arise is because the information about betweenness or analogical change is not accurate, or, more fundamentally, because it only takes the most salient properties of objects in the account. For example, when we derive betweenness information for wines from wine-food pairings, it will mainly reflect the taste of the wine, and to a much lesser extent properties such as price. As an additional example, we may consider that coffeehouses are conceptually between bars and restaurants, as both coffeehouses and bars emphasise drinking rather than eating, while coffeehouses generally do serve some food (sandwiches, cakes) as well. Nonetheless, we may consider that bar → serves-wine which is in conflict with the rule base. In this case, the inconsistency is mainly due the fact that the property of serving wine was not considered when asserting that coffeehouses are between bars and restaurants. The most natural way to avoid inconsistencies would then be to avoid applying interpolation to derive conclusions from the domain A = {serves-wine, ¬serves-wine}. In absence of any conflicts about attributes from a given domain, we then assume that interpolative and extrapolative conclusions are valid for that domain, an assumption which may need to be revised if additional knowledge became available.

Conclusions and future work

The aim of this paper was to study the core principles underlying interpolative and extrapolative reasoning about categorization rules. We have argued that sets of categorization rules can be seen as partial specifications of a linear mapping between conceptual spaces. This view has allowed us to describe interpolation and extrapolation at a purely qualitative level, relying on qualitative spatial relations to encode knowledge about conceptual spaces rather than on degrees of similarity.

From a practical point of view, the approach is motivated from the observation that sufficient data to estimate the conceptual relationship between labels from the same attribute domain is often available, e.g. relying on statistical techniques such as multi-dimensional scaling or singular-value decomposition, while knowledge about how different attribute domains are related is often sparse and is usually encoded in a symbolic form. The techniques presented in this paper show how knowledge about conceptual relations between labels of the same attribute domain may be leveraged to refine whatever symbolic knowledge of this kind we have. Although the general inference problem we have considered is PSPACE-hard, we have shown that efficient implementations in polynomial time are possible if the number of attribute domains is sufficiently small.

We may expect that the full generality of our framework would not be needed in many applications. In [START_REF] Prade | Completing rule bases in symbolic domains by analogy making[END_REF], for instance, an approach is presented to complete rule bases purely based on analogical proportions. The proposal from [START_REF] Prade | Completing rule bases in symbolic domains by analogy making[END_REF] in fact corresponds to a special case of the approach presented in this paper, where the only non-trivial information in Σ are assertions of the form par [START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF][START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF] (a, b, c; d) and par [START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF][START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF] (a, b, c; d). In [START_REF] Prade | Completing rule bases in symbolic domains by analogy making[END_REF] it is moreover assumed that all labels correspond to intervals in a uni-dimensional space, which implies that the relations par [START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF][START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF] and par [START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF][START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF] coincide, and moreover that they exhibit a number of symmetry and transitivity properties that are not generally valid (e.g. par [START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF][START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF] (a, b, c; d) iff par [START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF][START_REF] Kraus | Nonmonotonic reasoning, preferential models and cumulative logics[END_REF] (c, d, a; b)). These simplifications lead to an inference process which is easier to use in practice, but which is based on assumptions that are not always realistic. By putting the approach from [START_REF] Prade | Completing rule bases in symbolic domains by analogy making[END_REF] in relation to the approach from this paper, however, it immediately becomes apparent when these simplifications make sense, or how the approach should be adapted when they do not.

In contrast, some applications may require further generalizations of the approach we have presented here. At the level of the conceptual spaces, we have restricted ourselves to Euclidean spaces, whereas arbitrary metric spaces might be considered instead. Moreover, a better understanding is needed of which sets of assertions Σ are actually realizable, either in a Euclidean space or in an arbitrary metric space. Currently, no sound and complete procedures are available to check the consistency of such a set. Although this poses no problems when conceptual relations are obtained from geometric representations, consistency checking procedures may be important when other forms of acquisition are used (e.g. based on natural language processing). In addition to betweenness and parallelism, other types of conceptual relations may also be considered, as the same methodology may be applied to any type of spatial relation that is invariant under linear transformations. At the semantic level (Section 5), we have restricted ourselves to situations where only information about conceptual relation between individual labels is available. If, however, information would be available about the betweenness or parallelism of disjunctions of labels, a refined definition of bet and par should be used, as e.g. reg(b) may geometrically be between

reg(a 1 ) ∪ • • • ∪ reg(a p ) and reg(c 1 ) ∪ • • • ∪ reg(c q ) even if reg(b)
is not between reg(a i ) and reg(c j ) for any i and j. In such a case, the syntactic characterization of Section 6 should be adapted as well. Given the presented setting, however, such a generalization should be straightforward to formalize. This means in particular that as soon as m * (reg(x)) ∩ reg( y 0 ) = ∅ for a given x ∈ X and y 0 ∈ C, we must have that y 0 ∈ Y . In other words, we have that f (X) ⊆ Y , and since this holds for every Y satisfying (A.1), we obtain f (X) ⊆ f R (X). ✷ Proof of Proposition 2. Suppose that bet(reg( X 1 ), reg(Y ), reg( X 2 )) holds. Then there are x 1 ∈ reg( X 1 ), y ∈ reg(Y ) and x 2 ∈ reg( X 2 ) such that y is between x 1 and x 2 . Due to the fact that the labels of each attribute domain correspond to JEPD properties, there are (unique) elements a ∈ X 1 , b ∈ Y and c ∈ X 2 such that x 1 ∈ reg(a), y ∈ reg(b) and x 2 ∈ reg(c). To complete the proof, it suffices to show that for every i, it holds that bet(a i , b i , c i ), i.e. that there exist points x i ∈ reg(a i ), y i ∈ reg(b i ), and z i ∈ reg(c i ) such that y i is between x i and z i . As betweenness is preserved under projection, the points x i , y i and z i can be obtained from x, y and z after removing all irrelevant components. ✷ Proof of Proposition 3. Assume that Y ⊆ bet( X 1 , X 2 ). We need to show ∀q ∈ reg(Y ).∃p ∈ reg(X 1 ), r ∈ reg(X 2 ).(p = q) ∨ ∃λ ∈ [0, 1]. --→ pq = λ • -→ pr If q ∈ X 1 ∩ X 2 , we can simply take p = r = q. If q ∈ X 1 \ X 2 , then X 2 is realizable and we can take p = q and an arbitrary r ∈ reg( X 2 ) = ∅. Similarly, if q ∈ X 2 \ X 1 we can take p ∈ reg( X 1 ) = ∅ arbitrary and choose r = q.

For q ∈ reg({b | a ∈ X 1 , c ∈ X 2 , bet(a, b, c)}), note that the fact that bet(a, b, c) holds entails that the underlying attribute domains are all orthogonal (unless in the entirely trivial case where a = b = c). If a = b, it suffices to take p = q and let r be an arbitrary element from reg( X 2 ), and similar for the case where b = c. Otherwise, the vectors a = (a 1 , . . . , a l ), b = (b 1 , . . . , b l ) and c = (c 1 , . . . , c l ) only differ in the ith component for some i, and we have bet(a i , b i , c i ). Now, given bet(a i , b i , c i ), we know that for each q i ∈ reg(b i ) there are p i ∈ reg(a i ) and r i ∈ reg(c i ) such that q i is between p i and r i . As the attribute domains are orthogonal, and the vectors a, b and c agree on all but the ith component, it is easy to see that we then also have that for each q ∈ reg(b) there are p ∈ reg(a) and r ∈ reg(c) such that q is between p and r; it suffices to extend p i , q i and r i by choosing identical values for the added components. ), 1 i l, x ∈ D i }), we know by induction that for each i and q ′ ∈ reg(Y ↓i ) there are p ′ ∈ reg( X ↓i 1 ) and r ′ ∈ reg( X ↓i 2 ) such that q ′ is between p ′ and r ′ . By construction, we can extend q ′ to a point q ∈ reg(Y ) by choosing an arbitrary value for each of the quality dimensions underlying D i that do not already appear in q ′ . In the same way, we can then extend p ′ to p ∈ reg( X 1 ) and r ′ to r ∈ reg( X 2 ) by filling in the same values for the added quality dimensions. ✷ Proof of Proposition 4. Assume that Y ⊆ par( X 1 , X 2 , X 3 ). We need to show ∀s ∈ reg(Y ).∃p ∈ reg(X 1 ), q ∈ reg(X 2 ), r ∈ reg(X 3 ).∃λ 0. - → rs = λ • --→ pq If s ∈ X 1 ∩ X 2 ∩ X 3 , we can take p = q = r = s. If s ∈ (X 1 ∩ X 2 ) \ X 3 , we know that X 1 is realizable and thus reg( X 1 ) = ∅. We can then take p arbitrary and choose q = r = s. Similarly if s ∈ (X 1 ∩ X 3 ) \ X 2 , we can choose p = r = s and take q ∈ reg( X 2 ) = ∅ arbitrary. If s ∈ X 3 \ (X 1 ∪ X 2 ), we know that X 1 and X 2 are realizable, and we can take p ∈ reg( X 1 ) = ∅ and q ∈ reg( X 2 ) = ∅ arbitrary, and choose r = s. If s ∈ X 2 \ (X 1 ∪ X 3 ), we know that reg( X 1 ∩ X 3 ) = ∅, hence we can take an arbitrary r ∈ reg( X 1 ∩ X 3 ) and choose p = r and q = s.

For s ∈ reg({d | a ∈ X 1 , b ∈ X 2 , c ∈ X 3 , par(a, b, c; d)}), note that the fact that par(a, b, c; d) holds entails that the underlying attribute domains are all orthogonal (with the exception of the trivial case where a = b = c = d). If a = c and b = d, it suffices to take q = s and let p = r be an arbitrary element from reg(a) = reg(c). If c = d, we can take r = s and let p and q be arbitrary elements from reg(a) and reg(b) respectively. Otherwise, we have that the vectors a = (a 1 , . . . , a l ), b = (b 1 , . . . , b l ), c = (c 1 , . . . , c l ) and d = (d 1 , . . . , d l ) are such that for some j, it holds that par(a j , b j , c j ; d j ), whereas for all i = j we have a i = b i and c i = d i . From par(a j , b j , c j ; d j ) we know that there are points p j ∈ reg(a j ), q j ∈ reg(b j ), r j ∈ reg(c j ) and s j ∈ reg(d j ) such that ---→ r j s j = λ • ----→ p j q j for some λ 0. Given the orthogonality of the attribute domains and the fact that a i = b i for i = j, p j and q j can be extended to points p ∈ reg(a) and q ∈ reg(b) by choosing the same value for all added components. In the same way we can extend r j and s j to points r ∈ reg(c) and s ∈ reg(d) by choosing the same value for the added components. We then have that -→ rs = λ • --→ pq, with λ as before. For s ∈ reg({(d 1 , . . . , d i-1 , x, d i+1 , . . . , d l ) | d ∈ par( X ↓i 1 , X ↓i 2 , X ↓i 3 ), 1 i l, x ∈ D i }), we know by induction that for each i and s ′ ∈ reg(Y ↓i ) there are p ′ ∈ reg( X ↓i 1 ), q ′ ∈ reg( X ↓i 2 ) and r ′ ∈ reg( X ↓i 3 ) such that ---→ p ′ q ′ = λ • --→ r ′ s ′ for some λ > 0. By construction, we can extend s ′ to a point s ∈ reg(Y ) by choosing an arbitrary value for each of the quality dimensions underlying D i that do not already appear in s ′ . In the same way, we can then extend p ′ to p ∈ reg( X 1 ), q ′ to q ∈ reg( X 2 ) and r ′ to r ∈ reg( X 3 ) by filling in the same values for the added quality dimensions. The case where s ∈ reg({(d 1 , . . . , d i-1 , x, d i+1 , . . . , d l ) | d ∈ par( X ↓x 1 , X ↓y 2 , X ↓y 3 ), 1 i l, x ∈ D i , y ∈ D i , D i orthogonal to D 1 , . . . , D i-1 , D i+1 , . . . , D l }) is analogous, noting that the orthogonality of D i means that none of the attribute domains underlying D i will appear in s ′ , p ′ , q ′ and r ′ . ✷ Proof of Proposition 5. Suppose that par(reg( X 1 ), reg( X 2 ), reg( X 3 ); reg(Y )) holds. Then there are x 1 ∈ reg( X 1 ), x 2 ∈ reg( X 2 ), x 3 ∈ reg( X 3 ) and y ∈ reg(Y ) such that ---→

x 3 y = λ • ----→

x 1 x 2 holds. Due to the fact that the labels of each attribute domain correspond to JEPD properties, there are (unique) elements a ∈ X 1 , b ∈ X 2 , c ∈ X 3 and d ∈ Y such that x 1 ∈ reg(a), x 2 ∈ reg(b), x 3 ∈ reg(c) and y ∈ reg(d). To complete the proof, it suffices to show that for every i, it holds that par(a i , b i , c i ; d i ), i.e. that there exist points x 1 i ∈ reg(a i ), x 2 i ∈ reg(b i ), x 3 i ∈ reg(c i ) and y i ∈ reg(d i ) such that ----→

x 3 i y i = µ • ----→ x 1 i x 2
i for some µ 0. As parallelism is preserved under projection, the points x 1 i , x 2 i , x 3 i and y i can be obtained from x 1 , x 2 , x 3 and y after removing all irrelevant components, in which case the latter equality will hold for µ = λ. ✷

From f R (n+1) ({x}) ⊆ Y , by definition of f R (n+1) we have that there exist Y 1 , . . . , Y m , Z 1 , . . . , Z m , σ 1 , . . . , σ m , U 1 , . . . , U l , V 1 , . . . , V l , W 1 , . . . , W l and τ 1 , . . . , τ l such that

Y ⊇ f R {x} ∩ i bet σ i f R (n) (Y i ), f R (n) (Z i ) ∩ i par τ i f R (n) (U i ), f R (n) (V i ), f R (n) (W i ) (A.
a i ✶ σ i (b 1 ,...,b k )∈ f (n) R (Z j ) b i → (a 1 ,...,a k )∈bet σ j ( f (n) R (Y j ), f (n) R (Z j )) i
R (U j ), f (n) R (V j ), f (n) R (W j )) i a i
Using inference rules (I') and (E'), together this allows us to derive (R, Σ) ⊢ i x i → (a 1 ,...,a k )∈bet σ j ( f

(n) R (Y j ), f (n) R (Z j )) i a i (A.11) (R, Σ) ⊢ i x i → (a 1 ,...,a k )∈par τ j ( f (n) R (U j ), f (n) R (V j ), f (n) R (W j )) i a i (A.12)
Using inference rule (S), we find the trivial rule (R, Σ)

⊢ i x i → (a 1 ,...,a k )∈ f R ({x}) i a i (A.13)
By two repeated applications of (D) to combine (A.11), (A.12) and (A.13), we find (R, Σ) ⊢ i x i → (a 1 ,...,a k )∈bet σ j ( f

(n) R (Y j ), f (n) R (Z j )) i a i ∧ (a 1 ,...,a k )∈par τ j ( f (n) R (U j ), f (n) R (V j ), f (n) R (W j )) i a i ∧ (a 1 ,...,a k )∈ f R ({x}) i a i
Finally, from (A.10), it follows that we can apply (D) one more time to weaken the latter rule, from which we obtain (A.9). ✷

Proof of Proposition 14. The rule base R initially contains two types of rules. On the one hand, there is (84), whose antecedent corresponds to the outcome J , while on the other hand, there are rules of the form (82) and (83), whose antecedent does not correspond to any outcome at all. Clearly, non-trivial new rules can only be obtained from R by using interpolative reasoning. More specifically, initially, we can only combine the rule (84) with one of the other rules to yield a new rule r 1 , whose consequent is of the form y 1 ∨ y 2 and whose antecedent only differs from the antecedent of (84) in that an atom of the form x i has been replaced by x i , or an atom of the form x i has been replaced by x i . Moreover, this application of interpolation can only be applied if the antecedents of both (84) and r 1 satisfy the proposition p. Thus it is clear that the antecedent of r 1 corresponds to an outcome J 1 such that there is an improving flip from J to J 1 . We can then combine r 1 with some rule of the form (82) or (83) to obtain a new rule r 2 whose antecedent corresponds to an outcome J 2 such that there is an improving flip from J 1 to J 2 . It is thus clear that a rule of the form (85) can only be derived if there is a sequence of outcomes J , J 1 , . . . , J m , I that corresponds to a sequence of improving flips, i.e. if I dominates J .

Conversely, it is also clear that if there is an improving flip from J i to J i+1 , we will be able to derive the corresponding rule r i+1 once r i has been derived. ✷

Proof of Proposition 15. The proof is entirely analogous to the proof of Proposition 14. ✷ Proof of Proposition 16. By construction, it is clear that

f R (i+1) {x} ⊆ f R (i) {x} ∩ bet σ f R (i) set(α) , f R (i) set(γ ) | c 1 ∨ c 2 ∩ par τ f R (i) set(α) , f R (i) set(β) , f R (i) set(γ ) | c 3 ∨ c 4
To show that the inclusion also holds in the other direction, let Y and Z be subsets of B such that x ∈ bet σ (Y , Z ). We show that there are formulas α and γ such that condition c 1 or c 2 is satisfied and

f R (i) {x} ∩ bet σ f R (i) set(α) , f R (i) set(γ ) ⊆ bet σ f R (i) (Y ), f R (i) (Z ) (A.14)
First assume that all attribute domains are orthogonal. If x ∈ Y and 0 ∈ σ , then we will have f R

(i) {x} ⊆ bet σ f R (i) {x} , f R (i) (Z ) ⊆ bet σ f R (i) (Y ), f R (i) (Z )
and (A.14) is satisfied (regardless of the choice of α and γ ). Similarly, we find that (A.14) is satisfied if x ∈ Z and 1 ∈ σ . If x ∈ Y ∩ Z , we find for any (non-empty) σ that f R

(i) {x} ⊆ bet σ f R (i) {x} , f R (i) {x} ⊆ bet σ f R (i) (Y ), f R (i) (Z )
and therefore again (A.14). If there are y ∈ Y and z ∈ Z such that bet σ (y, x, z), then either we have y = x and 0 ∈ σ or y = z and 1 ∈ σ or x = y = z, which are already covered, or we have that c 1 or c 2 is satisfied for α = conj(y) and γ = conj(z). In the latter two cases we have

bet σ f R (i) set(α) , f R (i) set(γ ) ⊆ bet σ f R (i) (Y ), f R (i) (Z )
and thus also (A.14). Now assume that some attribute domains are not orthogonal, but that conj(x) = x j ∧ conj(x ′ ) with x ′ ∈ bet σ (Y ↓ j , Z ↓ j ). If

x ′ ∈ Y ↓ j , 0 ∈ σ and the remaining attribute domains are orthogonal, we have f R

(i) {x} ⊆ f R (i) set conj x ′ ⊆ bet σ f R (i) set conj x ′ , f R (i) (Z ) ⊆ bet σ f R (i) (Y ), f R (i) (Z )
The case where x ′ ∈ Z ↓ j and 1 ∈ σ is entirely analogous. If the remaining attribute domains are orthogonal and there are y ′ ∈ Y ↓ j and z ′ ∈ Z ↓ j such that bet σ (y ′ , x ′ , z ′ ), we can take α = conj(y ′ ) and γ = conj(z ′ ). The case where conj(x ′ ) =

x l ∧ conj(x ′′ ) with x ′′ ∈ bet σ (Y ↓ j↓l , Z ↓ j↓l ) is handled by repeating the same argument.

In entirely the same way, we show that for subsets X , Y and Z of B such that x ∈ par τ (X, Y , Z ), there exist conjunctions α, β and γ such that c 3 or c 4 is satisfied and

f R (i) {x} ∩ par τ f R (i) set(α) , f R (i) set(β) , f R (i) set(γ ) ⊆ par τ f R (i) (X), f R (i) (Y ), f R (i) (Z )
which completes the proof. ✷

Fig. 1 .

 1 Fig. 1. Modelling betweenness and parallelism between regions.

Fig. 3 .

 3 Fig. 3. The relations bet and par are not transitive.

Fig. 4 .

 4 Fig. 4. Qualitative description of a conceptual space of housing types.

  is sufficiently close to 1, for a, b and c the vector representations of three wine types a, b and c, and if --→ ab < -→ ac , we assume that the taste of wine b is between that of wines a and c. Similarly, if the cosine of the angle between --→ ab and -→

Fig. 5 .

 5 Fig. 5. Mappings from B (left) to C (right).

  to a conjunction of atoms at the syntactic level, hence subsets of D 1 × • • • × D l correspond to arbitrary formulas. Note that each subset of D 1 × • • • × D l indeed corresponds to a region in some underlying conceptual space D.

  on the parallelism of the vectors. The exceptions covered by the definition of par are the trivial case where a = c and b = d, the trivial case where c = d, and the case where the transition from a to b, and from c to d only affects one component. If the attribute domains D 1 , . . . , D l are not orthogonal, we cannot guarantee anything about the parallelism of elements from D 1 × • • • × D l , unless in the entirely trivial case where a = b = c = d. For any Cartesian product D 1 × • • • × D l of attribute domains, par is defined as par(a, b, c; d) iff ∀ j.par(a j , b j , c j ; d j )

  bet σ (a, b, c) ∈ Σ ⇒ bet σ reg(a), reg(b), reg(c) (39) bet σ reg(a), reg(b), reg(c) ⇒ bet σ (a, b, c) ∈ Σ * (40) par τ (a, b, c; d) ∈ Σ ⇒ par τ reg(a), reg(b), reg(c); reg(d) (41) par τ reg(a), reg(b), reg(c); reg(d) ⇒ par τ (a, b, c; d) ∈ Σ *

Example 17 .

 17 Using (par 1 ), we find Σ ⊢ bandol → zinfandel ✄ [0,+∞[ barbera, barolo (55) Σ ⊢ high-tannins → mid-tannins ✄ [0,+∞[ low-tannins, mid-tannins (56) Σ ⊢ full-body → medium-body ✄ [0,+∞[ light-body, medium-body (57) Using (par 10 ), we then obtain

Proposition 13 .Example 19 .

 1319 Let R, Σ , B and C be defined as before, and let X ⊆ B and Y ⊆ C. It holds that (R, Σ) ⊢ (x 1 ,...,x s )∈X i x i → (y 1 ,...,y k )∈Y i y i can be derived from (S), (I'), (E'), (D), (bet 1 )-(bet 9 ), (bet 1 )-(bet 6 ), (par 1 )-(par 12 ) and (par 1 )-(par 9 ) iff f R (X) ⊆ Y We can now formalize the inference about wines from Example 10. Using (S), we find

  ), we find using (I'): (R, Σ) ⊢ barbera → (low-tan ∨ mid-tan) ∧ med-body (77) If we then combine (77) with (71), (72), (55) and (64), using (E') gives us (R, Σ) ⊢ bandol → (mid-tan ∨ high-tan) ∧ (med-body ∨ full-body) (78) Combining (73), (74), (75), (59) and (65), we get using (E') (R, Σ) ⊢ mid-tan ∧ full-body → dark-red ∨ opaque (79) Similarly, combining (74), (75), (58) and (68) (R, Σ) ⊢ high-tan ∧ med-body → dark-red ∨ opaque (80) Repeatedly applying (D) to (75), (76), (79) and (80) yields (R, Σ) ⊢ (mid-tan ∨ high-tan) ∧ (med-body ∨ full-body) → dark-red ∨ opaque (81) which together with (78), gives us

d 2 }

 2 and A 3 = {a 3 , b 3 , c 3 , d 3 }. Assume furthermore that Σ only contains the assertions bet [0.5,0.5] (a 1 , b 1 , c 1 ), bet [0.5,0.5] (a 2 , b 2 , c 2 ) and bet [0.5,0.5] (a 3 , b 3 , c 3 ). Since R | a 1 → c 1 and R | a 3 → c 3 , using (S) and (I'), we find (R, Σ) ⊢ b 1 → b 3 . However, using R 1 only trivial information can be derived about b 1 , hence refining R 1 and R 2 separately does not allow us to derive anything about b 1 .

  Consider the following rules, which contain information about the amount of traffic (light, moderate, heavy) at different times during the day: morning → heavy-traffic (87) mid-day → moderate-traffic (88) evening → heavy-traffic (89) Using (I) and the assumption that mid-day → morning ✶ evening we then derive the rule

  restaurant → serves-wine (92) Using interpolation and the assumption coffeehouse → bar ✶ restaurant we derive the rule coffeehouse → serves-wine

1 .

 1 Let X ⊆ B and Y ⊆ C be such that R | A (x 1 ,...,x s )∈X s i=1 x i → (y 1 ,...,y k )∈Y and given that m * is a point-wise extension of the mapping m, we also have that x∈ X m * reg(x) ⊆ y∈Y reg( y)

Finally, for

  q ∈ reg({(b 1 , . . . , b i-1 , x, b i+1 , . . . , b l ) | b ∈ bet( X ↓i 1 , X ↓i 2

(a 1 (a 1

 11 ,...,a k )∈ f (n) R (U j ) a i ✄ τ j (b 1 ,...,b k )∈ f ,...,a k )∈proj τ j ( f (n)

  Left logical equivalence If α ≡ α ′ and α| ∼β then α ′ |∼β Right weakening If β | β ′ and α |∼ β then α| ∼β ′ OR If α| ∼γ and β|∼γ then α ∨ β|∼γ Cautious monotony If α| ∼β and α| ∼γ then α ∧ β|∼γ Cut If α ∧ β|∼γ and α| ∼β then α| ∼γ

  ⊢ bungalow ∨ villa ∨ mansion → medium ∨ large ∨ very-large and using (D) that (R, Σ) ⊢ villa → medium ∨ large ∨ very-large which refines the trivial conclusion that we obtained in

	(R, Σ) ⊢ large ∧ detached → lux
	(R, Σ) ⊢ large ∧ row-house → comf
	(R, Σ) ⊢ small ∧ detached → bas ∨ comf
	If we now assume that (writing det for detached)
	Example 5. Consider the rules from Example 2. Applying (S), we immediately have
	(R, Σ) ⊢ bungalow → medium	(R, Σ) ⊢ mansion → very-large
	Assuming
	Σ ⊢ bungalow ∨ villa ∨ mansion → bungalow ✶ mansion
	Σ ⊢ medium ✶ very-large → medium ∨ large ∨ very-large
	we find using (I) that
	(R, Σ) Example 2. Similarly, we find using (S) that

  f and f R be defined as before. It holds that

	f R	f

R

Moreover, if R is compatible with m in the sense of

[START_REF] Clementini | A reasoning system of ternary projective relations[END_REF]

, it follows from Postulates (bet1), (bet2), (par1) and (par2) that f f R Example 14. Let us again consider the rules from Example 2, and let us determine the comfort level of a medium-sized detached villa:

f R (villa, det, med)

  par [0,+∞[ (x ′ i , x i , x i ; x ) and par [0,+∞[ (x ′ i , x ′ i , x ; x i ) to Σ . In addition, we add par [0,+∞[ (y 0 , y 1 , y 1 ; y 2 ) par [0,+∞[ (y 2 , y 1 , y 1 ; y 0 ) par [0,+∞[ y -, y + , y 0 ; y 1 par [0,+∞[ y -, y + , y 0 ; y 2 par [0,+∞[ y -, y + , y 1 ; y 2 par [0,+∞[ y + , y -, y 2 ; y 1 par [0,+∞[ y + , y -, y 2 ; y 0 par [0,+∞[ y + , y -, y 1 ; y 0

	Proposition 15. Let I , J , N, R, and Σ be as above. It holds that I dominates J , given N, iff

  d) for each µ ∈ [0, +∞[ for which Σ contains relations of the form par [µ,µ] , and each a i 1 , . . . , a i r , b i 1 , . . . , b i r , c i 1 , . . . , c i r such that for each j it holds that par [µ,µ] (a i j , b i j , c i j ; x i j ) or a i j = b i j and c i j = x i j

	1) (set(γ )));

(

Corollary 2 .

 2 Let R, Σ , A 1 , . . . , A n , B 1 , . . . , B s and C 1 , . . . , C k be as before. Let β and γ be propositional formulas such that domains(β) ⊆ {B 1 , . . . , B s } and domains(γ ) ⊆ {C 1 , . . . , C k }. The problem of deciding whether (R, Σ) ⊢ β → γ is in EXPTIME. If the number of attribute domains n is upper bounded by a constant, this problem is in P.

  [START_REF] Shoham | A semantical approach to nonmonotonic logics[END_REF] and moreover x ∈ bet σ i (Y i , Z i ) for each i ∈ {1, . . . , m} and x ∈ par τ i (U i , V i , W i ) for each i ∈ {1, . . . , l}.By induction, we know that for each Y j , it holds that (R, Σ) ⊢ (y 1 ,...,y s )∈Y j i y i → (a 1 ,...,a k )∈ f and similar for Z j , U j , V j and W j . Furthermore, from x ∈ bet(Y i , Z i ) we find using Proposition 9 that (y 1 ,...,y s )∈Y j iy i ✶ σ i (z 1 ,...,z s )∈Z j i z iSimilarly, from x ∈ par(U j , V j , W j ), we find using Proposition 11 that

		a i
		(n) R (Y j ) i
	Σ ⊢	x i →
	i
	Σ ⊢	x i →
	i

(u 1 ,...,u s )∈U j i

u i ✄ τ i (v 1 ,...,v s )∈V j i v i , (w 1 ,...,w s )∈W j i w i

Using Proposition 10 and 12, we trivially derive

Σ ⊢ (a 1 ,...,a k )∈ f (n) R (Y j )

Throughout this paper, we use the terms concept and property interchangeably.

In particular, interpolative reasoning can be carried out w.r.t. any space for which betweenness can meaningfully be defined. See e.g.[START_REF] Aisbett | A general formulation of conceptual spaces as a meso level representation[END_REF] for a formalization of conceptual spaces in terms of a primitive betweenness relation.

This counterexample also illustrates a technical subtlety of the considered framework. If we want to represent the meaning of each label as a topologically closed set, then regions will inevitably share their boundary with other regions, which is not compatible with the view that different labels (of the same attribute domain) refer to pairwise disjoint properties. One solution to this problem is to associate with each label a topologically open region, and introduce topologically closed regions that correspond to borderline instances, i.e. instances for which it is hard to tell whether they belong to one concept or to another. In Fig.3(a), nothing prevents us from taking B and C to be topologically open regions.

http://www.last.fm.

http://randomnetstuff.com/wineplace/redwine.php, accessed July 28th, 2011.

We implicitly do assume that σ = ∅ however.

We implicitly do assume that τ = ∅ however.

Proof of Proposition 6. The proof is largely analogous to the proof of Propositions 3 and 4, except for the case of degenerate intervals. For that case, we need to verify that for λ ∈ [0, 1] and µ ∈ [0, +∞[, it holds that ∀i. bet [λ,λ] (a i , b i , c i ) ⇒ bet [λ,λ] [START_REF]The Analogical Mind: Perspectives from Cognitive Science[END_REF] provided that the underlying attribute domains D 1 , . . . , D l are all orthogonal. To show (A.2), suppose that bet [λ,λ] (a i , b i , c i )) for all i. This means that for every q i ∈ reg(b i ), there are p i ∈ reg(a i ) and r i ∈ reg(c i ) such that ---→ p i q i = λ • ---→ p i r i . Let these points be of the form p i = (p 1 i , . . . , p n i i ), q i = (q 1 i , . . . , q n i i ) and r i = (r 1 i , . . . , r n i i ). Now let q be a point from reg(b). Without lack of generality, given the fact that the attribute domains are orthogonal, we can assume that q is of the form (q 1 1 , . . . , q n 1 1 , . . . , q 1 l , . . . , q n l l ). We can moreover construct the points p = (p 1 1 , . . . , p n 1 1 , . . . , p 1 l , . . . , p n l l ) and r = (r 1 1 , . . . , r n 1 1 , . . . , r 1 l , . . . , r n l l ). By construction, we then have that p ∈ reg(a), r ∈ reg(c) and --→ pq = λ • -→ pr. As we can do this for every q ∈ reg(b), we have shown (A.2). The proof of (A.3) is entirely analogous. ✷

Proof of Proposition 7. The proof is entirely analogous to the proof of Propositions 2 and 5. ✷

Proof of Proposition 8. From the definitions of f R and f R we immediately find that

and thus f R f R . To show that f f R we show by induction that f f R (i) for all i ∈ N. The case where i = 0 was shown in Proposition 1. Assuming that we have already established f f R (i) , from the monotonicity of bet σ and par τ w.r.t. set inclusion we find that f R

where the last step follows from f ({x}) ⊆ f R ({x}) (since f f R by Proposition 1), together with [START_REF] Gérard | Ranking alternatives on the basis of generic constraints and examples: a possibilistic approach[END_REF] and [START_REF] Abraham | Analysis of the talmudic argumentum a fortiori inference rule (kal vachomer) using matrix abduction[END_REF]. Finally note that f (X) = x∈ X f ({x}) by definition of f . ✷ Proof of Lemma 1. Assume that α is strongly consistent, and let β be such that β | α, β is consistent, and all attribute domains in domains(β) are orthogonal. As set(β) ⊆ set(α) we also have (set(β) ↓i 1 ) ↓i 2 . . . ↓i s ⊆ (set(α) ↓i 1 ) ↓i 2 . . . ↓i s for all i 1 , . . . , i s . If the positions i 1 , . . . , i s refer to all attribute domains that are outside domains(β), then clearly (set(β) ↓i 1 ) ↓i 2 . . . ↓i s is non-empty and only contains components referring to orthogonal attribute domains anymore. This means that also (set(α) ↓i 1 ) ↓i 2 . . . ↓i s is non-empty and refers to orthogonal attribute domains, which means that set(α) is realizable. Conversely, assume that set(α) is realizable, then there exist positions i 1 , . . . , i s such that (set(α) ↓i 1 ) ↓i 2 . . . ↓i s is nonempty and only refers to orthogonal attribute domains. For b ∈ (set(α) ↓i 1 ) ↓i 2 . . . ↓i s we then find that conj(b) | α while all attribute domains in domains(conj(b)) are orthogonal, which means that α is strongly consistent. ✷ Proof of Proposition 9.

(⇒) Assume that Σ ⊢ α → β ✶ σ γ can be derived from the inference rules (bet 1 )-(bet 9 ). We show by induction that

If Σ ⊢ α → β ✶ σ γ was obtained from (bet 1 ), then α, β and γ are atoms and we have that bet σ (β, α, γ ) ∈ Σ , from which we find using (39) that bet σ (reg(β), reg(α), reg(γ )) holds which is the same as bet σ (set(β), set(α), set(γ )) because α, β and γ are atoms. We then easily find that set(α) ⊆ bet σ (set(β), set(γ )). Indeed, applying the definition of bet σ , given by ( 28), all attribute domains except for the one in which α, β and γ occur are deemed irrelevant, in which case bet σ (set(β), set(γ )) reduces to betweenness at the atom level.

In the case where Σ ⊢ α → β ✶ σ γ was obtained from (bet 3 ), we already have set(α) ⊆ bet 1-σ (set(γ ), set(β)). From the symmetry of the betweenness relation, we then immediately find that also set(α) ⊆ bet σ (set(β), set(γ )).

In the case where Σ ⊢ α → β ✶ σ γ was obtained from (bet 4 ), the strong consistency of β ensures that set(β) is realizable. By definition, we then have set(α) ⊆ bet σ (set(α), set(β)), given that 0 ∈ σ . The case where Σ ⊢ α → β ✶ σ γ was obtained from (bet 5 ) directly follows from the fact that we have set(α) ⊆ bet α (set(α), set(α)) for any α. Indeed, from [START_REF] Perfilieva | Interpolation of fuzzy data: Analytical approach and overview[END_REF]

If Σ ⊢ α → β ✶ σ γ was obtained from (bet 6 ), then there exist α 1 , α 2 , β 1 , β 2 , γ 1 and γ 2 such that α = α 1 ∨ α 2 , β = β 1 ∨ β 2 , γ = γ 1 ∨ γ 2 and, by induction, set(α 1 ) ⊆ bet σ (set(β 1 ), set(γ 1 )) and set(α 2 ) ⊆ bet σ (set(β 2 ), set(γ 2 )). Now, we have that

From the monotonicity of bet σ w.r.t. set inclusion, we find that the latter expression includes both bet σ (set(β 1 ), set(γ 1 )) and bet σ (set(β 2 ), set(γ 2 )), and thus also bet σ (set(β 1 ), set(γ 1 )) ∪ bet σ (set(β 2 ), set(γ 2 )), which in turn includes set(α 1 ) ∪ set(α 2 ). By definition of set the latter expression is equivalent to set(α 1 ∨ α 2 ) and thus to set(α).

If Σ ⊢ α → β ✶ σ γ was obtained from (bet 7 ), then there exist α ′ , β ′ , γ ′ and δ such that

), the proof is trivial, so assume that this were not the case. Since δ is strongly consistent, we can assume without lack of generality that the attribute domains in domains(δ) are orthogonal to each other (since if this were not the case, we could replace δ with a logically equivalent formula for which this is the case). Since the elements of domains(δ) are moreover orthogonal to the elements of domains(β ′ ) and domains(γ ′ ), it is not hard to see that bet σ (set

. Indeed, this is trivial if β ′ or γ ′ is not strongly consistent. If both are strongly consistent, then

If Σ ⊢ α → β ✶ γ was obtained from (bet 8 ), there are α 1 , α 2 , β 1 , β 2 , γ 1 and γ 2 such that α

Given the definition of bet [λ,λ] and given the fact that the attribute domains in domains(β 1 ) ∪ domains(γ 1 ) are orthogonal to those in domains(β 2 ) ∪ domains(γ 2 ), we can show that bet

) and (bet 2 ). Otherwise, given that (bet 2 ) entails syntax-independence, we can assume without lack of generality that α is of the form α 1 ∨ • • • ∨ α r , where each α i is a conjunction containing exactly one atom from each attribute domain. In other words, set(α i ) = {a} is a singleton. Because of inference rules (bet 6 ) and (bet 2 ), it suffices to show that Σ ⊢ α i → β ✶ σ γ can be derived for each i.

The fact that a ∈ bet σ (set(β), set(γ )) either means that (i) a ∈ set(β) ∪ set(γ ), (ii) there is a b ∈ set(β) and c ∈ set(γ ) such that bet σ (b, a, c) holds, or (iii) it holds that a ↓ j ∈ bet σ (set(β) ↓ j , set(γ ) ↓ j ) for some j, where we write a ↓ j for the vector a without the jth component and set(β) ↓ j and set(γ ) ↓ j are defined as in [START_REF] Hahmann | Multidimensional mereotopology with betweenness[END_REF].

In the first case, if a ∈ set(β) \ set(γ ) this means that set(γ ) is realizable and 0 ∈ σ (by ( 28)), hence that γ is strongly consistent (by Lemma 1). This means that we can derive Σ ⊢ α i → α i ✶ σ γ using (bet 4 ). Using (bet 2 ), we can then also conclude Σ ⊢ α i → β ✶ σ γ given that a ∈ set(β). In the same way, if a ∈ set(γ ) \ set(β), we derive Σ ⊢ α i → γ ✶ 1-σ β, and using (bet

In the second case, we clearly have that conj(b) | A β and conj(c) | A γ , hence because of inference rule (bet 2 ) it suffices to show that Σ ⊢ conj(a) → conj(b) ✶ σ conj(c) can be derived. By definition, bet σ (b, a, c) means that all components correspond to orthogonal attribute domains. First assume that σ is a non-degenerate interval. We then have that either (i) a = b, (ii) a = c, or (iii) that a differs only in one component from b and c, and that component in a is moreover between the corresponding components in b and c. In the latter situation, Σ ⊢ conj(a) → conj(b) ✶ σ conj(c) can clearly be derived using inference rules (bet 1 ) (given [START_REF] Aisbett | A general formulation of conceptual spaces as a meso level representation[END_REF]) and (bet 7 ), whereas when a = b, it can be derived using (bet 4 ), and when a = c it can be derived using (bet 4 ) and (bet 3 ). Now assume that σ = [λ, λ] is a degenerate interval. Then we have bet [λ,λ] (b i , a i , c i ) for every i, hence we can derive Σ ⊢ conj(a) → conj(b) ✶ σ conj(c) by repeatedly applying (bet 1 ) and then using (bet 8 ).

In the third case, note that set(β) ↓ j and set(γ ) ↓ j correspond to formulas β * and γ * such that β * | A β and γ * | A γ . Moreover, α i is of the form conj(a ↓ j ) ∧ x for some atom x, and in particular we have that α i | A conj(a ↓ j ). By induction, we can moreover assume that Σ ⊢ conj(a ↓ j ) → β * ✶ σ γ * can be derived. Using (bet 2 ) this means that also Σ ⊢ α i → β ✶ σ γ can be derived. ✷

Proof of Proposition 10.

(⇒) Assume that Σ ⊢ β ✶ σ γ → α can be derived from the inference rules (bet 1 )-(bet 6 ). We show by induction that then bet σ (set(β), set(γ )) ⊆ set(α).

If Σ ⊢ β ✶ σ γ → α was obtained from (bet 1 ), then it is not hard to see from [START_REF] Prade | Analogical proportions: another logical view[END_REF]

. By the fact that bet σ is clearly monotonic w.r.t. set inclusion, it follows that bet σ (set(β), set(γ )) ⊆ set(α).

The case where Σ ⊢ β ✶ σ γ → α was obtained from (bet 3 ) immediately follows from the definition of bet.

If Σ ⊢ β ✶ σ γ → α was obtained from (bet 4 ), then there exist α 1 , α 2 , β 1 and β 2 such that α = α 1 ∨α 2 , β = β 1 ∨β 2 , and, by induction, bet σ (set(β 1 ), set(γ )) ⊆ set(α 1 ) and bet σ (set

From the definition of bet σ it easily follows that the latter expression is equal to bet σ (set(β 1 ), set(γ )) ∪ bet σ (set(β 2 ), set(γ )). By the assumption, this latter expression is known to be included in set(α 1 ) ∨ set(α 2 ), which is equal to set(α).

If Σ ⊢ β ✶ σ γ → α was obtained from (bet 5 ), then there exist α 1 , α 2 , β 1 , β 2 , γ 1 and γ 2 such that α = α 1 ∧ α 2 , β = β 1 ∧ β 2 , γ = γ 1 ∧ γ 2 and, by induction, bet σ (set(β 1 ), set(γ 1 )) ⊆ set(α 1 ) and bet σ (set(β 2 ), set(γ 2 )) ⊆ set(α 2 ). Now we have that bet σ (set(

, set(γ 1 )) ⊆ set(α 1 ), using the monotonicity of bet σ w.r.t. set inclusion and using induction. For the same reason we also find bet σ (set(β

, which allows us to conclude that bet σ (set(

The case where Σ ⊢ β ✶ σ γ → α was obtained from (bet 6 ) is trivial. (⇐) Now we assume that bet σ (set(β), set(γ )) ⊆ set(α) and show that Σ ⊢ β ✶ σ γ → α can be derived from the inference rules (bet 1 )-(bet 6 ).

First assume that β is inconsistent, then Σ ⊢ β ✶ σ γ → α can be derived using (bet 6 ). If γ is inconsistent, then Σ ⊢ β ✶ σ γ → α can be derived using (bet 3 ) and (bet 6 ). If neither of β and γ is inconsistent (which implies that α cannot be inconsistent either), given that (bet 2 ) entails syntax-independence, we can assume without lack of generality

where each α i , β i and γ i is a conjunction containing exactly one atom from each attribute domain. In other words, set(α i ) = {a i }, set(β i ) = {b i } and set(γ i ) = {c i } are singletons. By definition of bet σ , we then have that bet σ (set(β), set(γ )) = i, j bet σ (b i , c j ). In particular, we also find that for every i and j there are k 1 , . . . , k l such that bet σ (b i , c j ) ⊆ {a k 1 , . . . , a k l }. The latter inclusion means that every component of each of a k 1 , . . . , a k l is between the corresponding components of b i and c j , and furthermore that there are no other such vectors. Using (bet 1 ) (given (44)) and (bet 5 ) we can therefore derive that Σ ⊢

and by (bet 2 ) that Σ ⊢ β i ✶ γ j → α. As we can derive this for every i and j, (bet 4 ) finally allows us to derive Σ ⊢ β ✶ γ → α. ✷ Proof of Proposition 11.

(⇒) Assume that Σ ⊢ δ → γ ✄ τ α, β can be derived from the inference rules (par 1 )-(par 12 ). We show by induction that then set(δ) ⊆ par τ (set(α), set(β), set(γ )).

If Σ ⊢ δ → γ ✄ τ α, β was obtained from (par 1 ), then α, β, γ and δ are atoms and we have from (41) that par τ (α, β, γ ; δ) holds, from which we find set(δ) ⊆ par τ (set(α), set(β), set(γ )). If Σ ⊢ δ → γ ✄ τ α, β was obtained from (par 2 ), then there exist α ′ , β ′ , γ ′ , δ ′ and τ ′ such that α

, and set(δ) ⊆ set(δ ′ ). By the fact that par τ is clearly monotonic w.r.t. set inclusion, it follows that set(δ) ⊆ par τ (set(α), set(β), set(γ )).

The case where Σ ⊢ δ → γ ✄ τ α, β was obtained from (par 3 ) follows immediately from the definition of par τ , given that the strong consistency of α implies that set(α) is realizable (by Lemma 1).

The case where Σ ⊢ δ → γ ✄ τ α, β was obtained from (par 4 ) follows immediately from the fact that par τ (X 1 , X 2 , X 3 ) ⊇ X 1 ∩ X 2 ∩ X 3 according to [START_REF] Sheremet | Comparative similarity, tree automata, and diophantine equations[END_REF].

The cases where Σ ⊢ δ → γ ✄ τ α, β was obtained from (par 5 ), (par 6 ), (par 7 ) and (par 8 ) are entirely analogous. If Σ ⊢ δ → γ ✄ τ α, β was obtained from (par 9 ), then there exist α 1 , α 2 , β 1 , β 2 , γ 1 , γ 2 , δ 1 and δ 2 such that α = α 1 ∨ α 2 , β = β 1 ∨ β 2 , γ = γ 1 ∨ γ 2 , δ = δ 1 ∨ δ 2 and, by induction, set(δ 1 ) ⊆ par τ (set(α 1 ), set(β 1 ), set(γ 1 )) and set(δ 2 ) ⊆ par τ (set(α 2 ), set(β 2 ), set(γ 2 )). We have

From the monotonicity of par τ it easily follows that

If Σ ⊢ δ → γ ✄ τ α, β was obtained from (par 10 ), then there exist α ′ , β ′ and φ such that α = α ′ ∧ φ and β = β ′ ∧ φ and, by induction, set(δ) ⊆ par τ (set(α ′ ), set(β ′ ), set(γ )). Without lack of generality, we can assume that the elements from domains(φ) are all orthogonal to each other (because φ was assumed to be strongly consistent), and that φ = φ 1 ∨ • • • ∨ φ s is in disjunctive-normal form. Because of (par 9 ), it is sufficient to show that set(δ) ⊆ par τ (set(α ∧ δ i ), set(β ∧ δ i ), set(γ )) for each i. Since these elements from domains(δ) are assumed to be orthogonal to the elements of domains(α) ∪ domains(β) ∪ domains(γ ) ∪ domains(δ), however, the latter inclusion follows easily from the definition of par τ , given that we already know that set(δ) ⊆ par τ (set(α ′ ), set(β ′ ), set(γ )).

The case where (par 11 ) is entirely analogous to the case for (par 8 ) in the proof of Proposition 9.

The case where Σ ⊢ δ → γ ✄ τ α, β was obtained from (par 12 ) is trivial.

(⇐) Now we assume that set(δ) ⊆ par τ (set(α), set(β), set(γ )) and show that Σ ⊢ δ → γ ✄ τ α, β can be derived from the inference rules (par 1 )-(par 12 ). If either of α, β or γ is inconsistent, then we must have that set(δ) = ∅, i.e. that δ is inconsistent as well. This means that Σ ⊢ δ → γ ✄ τ α, β can be derived from (par 12 ) and (par 2 ).

If α, β and γ are consistent, given that (par 2 ) entails syntax-independence, we can assume without lack of generality that δ is of the form δ 1 ∨ • • • ∨ δ r , where each δ i is a conjunction containing exactly one atom from each attribute domain. In other words, set(δ i ) = {d} is a singleton. Because of inference rules (par 9 ) and (par 2 ), it suffices to show that Σ ⊢ δ i → γ ✄ τ α, β can be derived for each i.

The fact that d ∈ par τ (set(α), set(β), set(γ )) either means that (i) d ∈ set(β) ∪ set(γ ), (ii) there is an a ∈ set(α), b ∈ set(β) and c ∈ set(γ ) such that par τ (a, b, c; d) holds, (iii) it holds that d ↓ j ∈ par τ (set(α) ↓ j , set(β) ↓ j , set(γ ) ↓ j ) for some j, where we write d ↓ j for the vector d without the jth component and set(α) ↓ j , set(β) ↓ j and set(γ ) ↓ j are defined as in [START_REF] Hahmann | Multidimensional mereotopology with betweenness[END_REF], or (iv) it holds that d ↓ j ∈ par τ (set(α) ↓ j , set(β) ↓y , set(γ ) ↓y ) for some j and some y from the corresponding attribute domain.

In the first case, if moreover d ∈ set(β) ∩ set(γ ) ∩ set(α), we can derive Σ ⊢ δ i → δ i ✄ τ δ i , δ i using (par 4 ), and subsequently also that Σ ⊢ δ i → γ ✄ τ α, β using (par 2 ). If d ∈ (set(β) ∩ set(γ )) \ set(α), we know that α is strongly consistent and 0 ∈ τ , which means that we can derive Σ ⊢ δ i → δ i ✄ τ α, δ i using (par 8 ) and thus Σ ⊢ δ i → γ ✄ τ α, β using (par 2 ). The case where d ∈ (set(α) ∩ set(γ )) \ set(β) is entirely analogous (using (par 7 ) instead of (par 8 )).

, we know that α ∧ γ is strongly consistent and 1 ∈ τ , hence we can derive Σ ⊢ δ i → α ∧ γ ✄ τ α ∧ γ , δ i using (par 3 ) and again Σ ⊢ δ i → γ ✄ τ α, β using (par 2 ). If d ∈ set(γ ) \ (set(α) ∪ set(β)), we know that either α and β are strongly consistent and 0 ∈ τ or that α ∧ β is strongly consistent, hence we can either derive Σ ⊢ δ i → δ i ✄ τ α, β using (par 6 ), or we can derive Σ ⊢ δ i → δ i ✄ τ α ∧ β, α ∧ β using (par 5 ). In both cases, we then find Σ ⊢ δ i → γ ✄ τ α, β using (par 2 ).

In the second case, we clearly have that conj(a

, conj(b) can be derived. From the definition of par τ , we know that all components correspond to orthogonal attribute domains. Moreover, either

• a differs only in one component from b, c differs from d only in that same component, and the respective values a j , b j , c j , d j of the component satisfy par τ (a j , b j , c j ; d j ),

• τ = [µ, µ] is a degenerate interval, and for each component j, it holds that par τ (a j , b j , c j ; d j ).

In the situation where a = c and b = d, we can derive Σ ⊢ conj(d) → conj(c) ✄ τ conj(a), conj(b) using (par 3 ). In the second situation, we can use (par 6 ). In the third situation, it is clear that Σ ⊢ conj(d) → conj(c) ✄ τ conj(a), conj(b) can be derived by first applying inference rule (par 1 ) (given [START_REF] Billen | On the Move to Meaningful Internet Systems[END_REF]) and then applying inference rule (par 10 ). In the last situation, we can similarly derive Σ ⊢ conj(d) → conj(c) ✄ τ conj(a), conj(b) using (par 11 ) instead of (par 10 ).

In the third case, note that set(α) ↓ j , set(β) ↓ j and set(γ ) ↓ j correspond to formulas α * , β * and γ * such that α * | A α, β * | A β and γ * | A γ . Moreover, δ i is of the form conj(d ↓ j ) ∧ x for some atom x, and in particular we have that

. By induction, we can moreover assume that Σ ⊢ conj(d ↓ j ) → γ * ✄ τ α * , β * can be derived. Using (par 2 ) this means that also Σ ⊢ δ i → γ ✄ τ α, β can be derived.

In the fourth case, we have that set(α) ↓ j , set(β) ↓ j and set(γ ) ↓ j correspond to formulas α * , β * and γ * such that α * | A α, β * ∧ y | A β and γ * ∧ y | A γ . Using (par 10 ) (for ψ = ⊤ and φ = y) and (par 2 ), we again find that Σ ⊢ δ i → γ ✄ τ α, β can be derived. ✷

Proof of Proposition 12.

(⇒) Assume that Σ ⊢ γ ✄ τ α, β → δ can be derived from the inference rules (par 1 )-(par 9 ). We show by induction that then par τ set(α), set(β), set(γ ) ⊆ set(δ)

If Σ ⊢ γ ✄ τ α, β → δ was obtained from (par 1 ), then it is not hard to see from [START_REF] Gärdenfors | Reasoning about categories in conceptual spaces[END_REF] that set(δ) = {d | par τ (a, b, c; d), a ∈ set(α), b ∈ set(β), c ∈ set(γ )}, from which we immediately find par τ set(α), set(β), set(γ ) ⊆ set(δ)

By induction, we then have that

. By the fact that par τ is clearly monotonic w.r.t. set inclusion, it follows that par τ (set(α), set(β), set(γ )) ⊆ set(δ).

If Σ ⊢ γ ✄ τ α, β → δ was obtained from (par 3 ), then there exist α 1 , α 2 , δ 1 and δ 2 such that α = α 1 ∨ α 2 , δ = δ 1 ∨ δ 2 and, by induction, par τ (set(α 1 ), set(β), set(γ )) ⊆ set(δ 1 ) and par τ (set(α 2 ), set(β), set(γ )) ⊆ set(δ 2 ). Now, we have that par τ (set(α), set(β), set(γ )) = par τ (set(α 1 ) ∪ set(α 2 ), set(β), set(γ )). From the definition of par τ it easily follows that the latter expression is equal to

By the assumption, this latter expression is known to be included in set(δ 1 ) ∨ set(δ 2 ), which is equal to set(δ).

The cases where Σ ⊢ γ ✄ τ α, β → δ was obtained from (par 4 ) or from (par 5 ) are entirely analogous. If Σ ⊢ γ ✄ τ α, β → δ was obtained from (par 6 ), then there exist α 1 , α 2 , β 1 , β 2 , γ 1 , γ 2 , δ 1 and δ 2 such that α = α 1 ∧ α 2 , β = β 1 ∧ β 2 , γ = γ 1 ∧ γ 2 , δ = δ 1 ∧ δ 2 and, by induction, par τ (set(α 1 ), set(β 1 ), set(γ 1 )) ⊆ set(δ 1 ) and par τ (set(α 2 ), set(β 2 ), set(γ 2 )) ⊆ set(δ 2 ). Given the monotonicity of par w.r.t. set inclusion, we have that

⊆ set(δ 1 )

which leads to par τ (set(α), set(β), set(γ )) ⊆ set(δ).

The cases where Σ ⊢ γ ✄ τ α, β → δ was obtained from (par 7 ), (par 8 ) or (par 9 ) are trivial. (⇐) Now we assume that par τ (set(α), set(β), set(γ )) ⊆ set(δ) and show that Σ ⊢ γ ✄ τ α, β → δ can be derived from the inference rules (par 1 )-(par 9 ). If α, β or γ is inconsistent, Σ ⊢ γ ✄ τ α, β → δ can be inferred immediately using (par 7 )-(par 9 ) and (par 2 ).

If neither of α, β and γ is inconsistent, given that (par 2 ) entails syntax-independence, we can assume without lack of generality that α

where each α i , β i , γ i and δ i is a conjunction containing exactly one atom from each attribute domain. In other words, set

By definition of par τ , we then have that par τ (set(α), set(β), set(γ )) = i, j,l par τ (a i , b j , c l ). In particular, we also find that for every i, j and l there are k 1 , . . . , k r such that par τ (a i , b j , c l ) ⊆ {d k 1 , . . . , d k r }. The latter inclusion means that the respective components of a i , b j , c l on the one hand and d k 1 , . . . , d k r on the other hand all define parallel directions, and in particular that we can derive Σ ⊢ γ l ✄ τ α i , β j → δ k 1 ∨ • • • ∨ δ k r using inference rules (par 1 ) (considering that [START_REF] Pawlak | Rough Sets: Theoretical Aspects of Reasoning about Data[END_REF]) and (par 6 ). As we can do this for all i, j and l, (par 3 ), (par 4 ) and (par 5 ) allow us to derive Σ ⊢ γ ✄ τ α, β → δ. ✷ Proof of Proposition 13. Before we move to the actual proof, we introduce some notations. Recall that for any formula α, set(α) was defined to be a subset of A. However, if domains(α) ⊆ {B 1 , . . . , B s }, then the attribute domains in {C 1 , . . . , C k } \ {B 1 , . . . , B s } are redundant, as they are not constrained by α. Throughout the proof, we will use the notation set B (α) to denote the restriction of the vectors in set(α) to the components corresponding to attribute domains from B, and similar for the notation set C (α). For a vector x ∈ A, we also write x B and x C for its restriction to the attribute domains in {B 1 , . . . , B s } and in {C 1 , . . . , C k } respectively. Moreover, it should be clear from the definition of e.g. bet σ that when domains(β 1 ) ⊆ {B 1 , . . . , B s }, domains(β 2 ) ⊆ {B 1 , . . . , B s }, and bet σ (set(β 1 ), set(β 2 )) then we also have bet σ (set B (β 1 ), set B (β 2 )), and similar for bet σ , par σ and par σ , and for situations where the attribute domains are restricted to {C 1 , . . . , C k }. [START_REF] Dubois | What are fuzzy rules and how to use them[END_REF] we show that f R (set B (β)) ⊆ set C (γ ) using structural induction. Note that the soundness part of the proposition follows from this, as

If the right-hand side of (A.4) has been obtained using (S), we have

2. Assume that the last inference rule that was applied to obtain (A.4) was (I'). Then there are β 1 , β 2 , γ 1 and γ 2 such that (R, Σ 3. The case where (E') is the last inference rule that was applied is entirely analogous.

4. Assume that the last inference rule that was applied to obtain (A.4) was (D). Then there are formulas β 1 , β 2 , γ 1 , and γ 2 such that (R, Σ) ⊢ β 1 → γ 1 (A.5) (R, Σ) ⊢ β 2 → γ 2 (A.6)

Without lack of generality, we can assume that domains(β 1 ) and domains(β 2 ) are subsets of {B 1 , . . . , B s }, while domains(γ 1 ) and domains(γ 2 ) are subsets of {C 1 , . . . , C k }.

Let x ∈ set B (β). First suppose that x ∈ set B (β 1 ) and x / ∈ set B (β 2 ). By induction, we know that f R (x) ⊆ set C (γ 1 ). From (A.7), we moreover know that for every a in A such that a B = x and a C ∈ set C (γ 1 ), it holds that a C ∈ set C (γ ). This means that f R (x) ∩ set C (γ 1 ) ⊆ set C (γ ). Together with f R (x) ⊆ set C (γ 1 ), this means in particular that f R (x) ⊆ set C (γ ). Entirely analogously, we find f R (x) ⊆ set C (γ ) when x / ∈ set B (β 1 ) and x ∈ set B (β 2 ). If x ∈ set B (β 1 ) and x ∈ set B (β 2 ), we find f R (x) ⊆ set C (γ 1 ) ∩ set C (γ 1 ). For every a in A such that a B = x, a C ∈ set C (γ 1 ) and a C ∈ set C (γ 2 ), it then holds that a C ∈ set C (γ ) due to (A.7). Again this leads to f R (x) ⊆ set C (γ ). To show the induction step, because of inference rule (D), it suffices to show that for each x = (x 1 , . . . , x n ) in X , it holds that (R, Σ) ⊢ i x i → (y 1 ,...,y k )∈Y i y i (A.9)