The management of multiple sources of information raises many fusion problems due to the uncertainty and the heterogeneity: geographical information combines all of them [3,14,1], one specific aspect being to deal with geo-located parcels that are shareable by all sources. The "field model": (x, y) → f (x, y), though widely used in applications that involve imagery or gridded data, is much too limited in situations that deal with non quantitative data, such as landscape analysis. Spatial information may involve a mix of numeric and symbolic attributes, using different vocabularies, from more or less structured, but never unstructured, dictionaries. The sources may use different space partitions, and there may exist several kinds of dependencies, then the spatial fusion must keep consistent with all of them. After our informal discussion of this issue in [4], we now provide a logical framework for handling spatial and ontological information.
The novelty is to handle the merging of spatial information in the general setting of logical information fusion.
Because both numeric and symbolic information may be pervaded by uncertainty and imprecision [11], we must allow for "uncertain attributive formulas", to express that for any parcel of a given set, we know at some degree that a property is true. We can also distinguish between what holds everywhere, or only somewhere in a parcel. Hence, dealing with spatial data requires relatively powerful representation languages [12]. Ontology is often used for representing structured vocabularies [9], and merging geospatial information must face the problem of heterogeneous ontologies [7]. Therefore, terminology integration, based on learning data, and information fusion, based on multiple space partitions, are two classical steps in many geographical applications.
Following [18], we use a logical framework for processing ontologies, and "attributive formulas" that link sets of parcels to set of properties. Only three conditions are required: 1) a label can be a sub-label of another label, 2) a label is the reunion of its sub-labels, 3) labels referring to the most specific classes are mutually exclusive two by two. This representation language can express both ontological information and attributive formulas. But spatial information may vary in spatial extent even within a parcel. Indeed, we show that while inheritance relations can safely be integrated by attributive formulas, terminological mutual exclusion cannot, unless under an explicit and precise reading: everywhere, or somewhere.
In geographic information we should distinguish the geo part, the info part, and the association that links them (the what, the there and the is, of Quine [15]):
1) the (attributed) space: one space for all applications, but many different ways to split it into parts. We limit our study to parcels that have a spatial extent, and to the finite case where, after intersection, the most elementary parcels form a finite partition of the space. This is often referred to as a partonomy structure.
2) the (attribute) properties: many property domains, more or less independent, can serve different purposes. A taxonomy structure can represent a hierarchy of properties, reflecting a partial order. A consistent fusion of partial orders may help to detect, and to remove errors when mixing such structures.
3) the attribution: in a complex observation process, associations are multiple in general, and largely pervaded by uncertainty on both parcels and properties.
A similar, but informal approach was proposed in [13]: an ontology is suggested building on three main concepts: (1) a partonomy of physical objects of which the attributes represent most of the relevant information, (2) a simple taxonomy of informational objects, (3) a relation between the informational objects and those physical objects they inform about. Hence the "relational model" is more appropriate than the "field model", to represent the property-parcel link. There are two other basic links that the relational model can satisfactory encode: property-property (from the knowledge encoded in a property taxonomy), and parcel-parcel (from a partonomy).
Handling fusion requires further combination. Let { set of nodes , ⊆} be a poset: nodes are concepts, and edges are specialization/subsumption relations. Let L a propositional logic language built on a vocabulary V with the usual connectives: ∧, ∨, →.
Definition 1 (poset definition of an ontology). An ontology is a directed acyclic graph (dag) G = (X, U ). X ⊆ L is a set of formulas (one per concept); U is a set of directed arcs (ϕ, ψ) denoting that ϕ is a subclass of ψ. An ontology admits one single source, ⊥, and one single sink .
Definition 2 (leaves and levels in an ontology). Levels are defined inductively: L 0 is the set of formulas that have no predecessor: (⊥, ϕ) ∈ U , called leaves, L i is the set of formulas that have no predecessor in G \ (L 0 ∪ . . . L i−1 ), etc. Let Γ + (x) and Γ − (x) be the set of successors and predecessors of x.
Moreover, we impose: (a) G: to be a lattice, (b) all the sub-classes of a class: to appear in the ontology, (c) all the leaves: to be mutually exclusive two by two.
Proposition 1. Providing that:
(1) we add the appropriate formulas and arcs that turn a dag into a lattice;
(2) we add to each not-leave formula ϕ, a sub-formula "other elements of ϕ";
(3) we split leaves, wherever necessary, to make them mutually exclusive; then, we can insure conditions (a), (b) and (c), because the operations (1), ( 2) and ( 3) can always be done in the finite case.
Hence, an ontology will be encoded in the following way. Definition 3 (logical encoding of an ontology). Any dag G = (X, U ) representing an ontology can be associated to a set L G of formulas that hold:
Rule 1 expresses that an inclusion relation holds between two classes, 2 is a kind of closed world assumption version of property (b), 3 expresses property (c), 4 expresses completeness, as follows: if all the inclusion relations are known in the ontology, hence all corresponding paths must exist in G. From this, it follows that: ∀ϕ ∈ X, ϕ → ϕi∈Γ + (ϕ) ϕ i . and ∀ϕ ∈ X, ϕ → .
This formalization of an ontology [16] can be applied to parcels, to provide a partonomy, and to properties to provide a taxonomy. Their leaves are named respectively partons, and taxons. Since we need binary links, our language is built on ordered pairs of formulas of L i × L s , here denoted (ϕ, p). Such formulas should be understood as formulas of L i reified by association with a set of parcels described by a formula of L s . In other words, to each formula is attached a set of parcels, where this formula applies. Definition 4 (attributive formula). An attributive formula f , denoted by a pair (ϕ, p), is a propositional language formula based on the vocabulary V i ∪ V s where the logical equivalence f ≡ ¬p ∨ ϕ holds and p contains only variables of the vocabulary V s (p ∈ L s ) and ϕ contains only variables of V i (ϕ ∈ L i ).
The intuitive meaning of (ϕ, p) is: for the set of elementary parcels that satisfy p, the formula ϕ is true. Observe that there exist formulas built on the vocabulary V i ∪ V s which cannot be put under the attributive form, e.g., a ∧ p 1 where a is a literal of V i and p 1 a literal of V s . The introduction of connectives ∧, ∨ and ¬ does make sense, since any pair (ϕ, p) is a classical formula. From the above definition of (ϕ, p) as being equivalent to ¬p ∨ ϕ, several inference rules straightforwardly follow from classical logic: Proposition 3 (inference rules on attributive formulas).
¿From these rules, we can deduce the converse of 2: (ϕ ∧ ϕ , p) (ϕ, p), (ϕ , p) and that (ϕ, p), (ψ, p ) (ϕ ∨ ψ, p ∨ p ) and (ϕ, p), (ψ, p ) (ϕ ∧ ψ, p ∧ p ).
Remark: the reification allows us to keep inconsistency local.
The vocabulary is often insufficient for describing taxons in a non-ambiguous way. Conversely there may be no proper set of parcels that uniquely satisfies a given set of properties. Therefore, only many-to-many relationships are really useful for representing geographic information. Then, between the parcels of a given subset P i of the partonomy, and the properties of a given list L j excerpted from the taxonomy, we need classically to build three relations:
-R s that distributes the subset P i over its parcels; -R p that distributes the subset L j over its properties; -R a made of the attributive formulas: pairs from R s × R p (learning samples). Formal Concept Analysis (FCA [17,10]) uses R a to build a Galois lattice, with all the pairs (extension, intention), named concepts, whose components are referring to each other bi-univoquely. A partonomy of parcels, and a taxonomy of properties, can be computed by FCA, from a specific R a . More interesting is to discover if some additional knowledge emerges from the fusion of two information sources: (R s1 ,R p1 ,R a1 ) and (R s2 ,R p2 ,R a2 ). The fusion of partonomies is easy, if we can neglect data matching issues: the geometric intersections between parcels of R s1 and R s2 , become leaves of the fusion R s . The fusion of taxonomies is more difficult: an important literature (semantic web, etc.) converges now to the notion of ontology alignment [8]. We distinguish: (a) the concatenation R a = R a1 +R a2 , (b) the structural alignment that identifies candidate concepts for attributive formulas, and their partial order (FCA); (c) the labeling of concepts, either from T 1 or T 2 , or by coupling (sign &) concepts from both; (d) the decision to keep or discard these candidate nodes, according to one or several criteria.
In land cover analysis, when experts from two disciplines build a domain ontology that reflects their respective knowledge, often it results in concurrent taxonomies, as in Fig. 1: taxonomy T 1 seems broader than taxonomy T 2 , which focuses on moorlands, and T 1 accepts multi-heritage, while T 2 doesn't. One approach -"mutual exclusion"-is to concatenate the taxonomies, under the assumption that they are disjoint, and that only one label is allowed, from whatever vocabulary: it is the smallest one, but isn't practicable, e.g.: agriculture and herbaceous aren't necessarily exclusive. Another approach -"cross-product"-is to consider as equally possible, every couple of labels compatible with both original partial orders: it doesn't impose anything, hence, it doesn't provide any new information.
Better solution -"aligned taxonomy"-: to use the relation R a , built for each p, by concatenating all the attributive formulas (ϕ 1 i , p) on T 1 , with all (ϕ 2 i , p) on T 2 for the same p. A regular FCA algorithm can compute Fig. 2: this more informative solution filters only the concepts that fit with the actual observations, i.e.: the original nodes plus only 4 new cross-product nodes. When uncertainty takes place, attribute values of objects may become ill-known, and should be represented by distributions over possible values: -In a relational database, the distributions are defined on attribute domains.
-In formal concept analysis only boolean values can refer to the fact that the object has, or not, the property. -In the logical language, formulas are associated to certainty levels that together define constraints on underlying distributions over interpretations. It allows to represent disjunctions, and that some alternatives are more likely than others.
We want also to detail the behaviour of a property within a parcel that has a spatial extent: it can apply either to the whole parcel, or only to a sub-part.
Our attributive language is extended in a possibilistic logic manner, by allowing uncertainty on properties. Let us recall that a standard propositional possibilistic formula [5] is a pair made of a logical proposition (Boolean), associated with a certainty level. The semantic counterpart of a possibilistic formula (ϕ, α) is a constraint N (ϕ) ≥ α expressing that α is a lower bound on the necessity measure N [6] of logical formula ϕ. Possibilistic logic has been proved to be sound and complete with respect to a semantics expressed in terms of the greatest possibility distribution π underlying N (N (ϕ) = 1 − sup ω|=¬ϕ π(ω)). This distribution rank-orders interpretations according to their plausibility [5].
Note that a possibilistic formula (ϕ, α) can be viewed at the meta level as being only true or false, since either N (ϕ) ≥ α or N (ϕ) < α. This allows us to introduce possibilistic formula instead of propositional formula inside our attributive pair, and leads to the following definition.
). An uncertain attributive formula is a pair ((ϕ, α), p) meaning that for the set of elementary parcels that satisfy p, the formula ϕ is certain at least at level α.
The inference rules of possibilistic logic [5] straightforwardly extend into the following rules for reasoning with uncertain attributive formulas: Proposition 4 (inference rules on uncertain attributive formulas).
Rules 3.A-B correspond to the fact that either i) we locate ourselves in the parcels that satisfy both p and p , and then the certainty level of ϕ can reach the maximal upper bound of the certainty levels known in p or in p , or ii) we consider any parcel in the union of the models of p and p and then the certainty level is only guaranteed to be greater than the minimum of α and β.
Still, attributive information itself may have two different intended meanings, namely when stating (ϕ, p) one may want to express that:
everywhere in each parcel satisfying p, ϕ holds as true, denoted by (ϕ, p, e).
Then, for instance, (Agriculture, p, e) cannot be consistent with (F orest, p, e) since "Agriculture" and "Forest" are mutually exclusive in taxonomy 1. somewhere in each parcel satisfying p, ϕ holds as true, denoted by (ϕ, p, s).
Then, replacing e by s in this example is no longer inconsistent, since in each parcel there may exist "Agricultural" parts and "Forest" parts.
Note that these two meanings differ from the case where two exclusive labels such as "Water" and "Grass" might be attributed to the same parcel because they are intimately mixed, as in a "Swamp". This latter case should be handled by adding a new appropriate label in the ontology. More formally, for a given parcel p in the partonomy, if p is: -not a leave, (ϕ, p, s) means: ∀p , p p, (ϕ, p , s) holds; -a leave, but made of parts o, (ϕ, p, s) means that ∃o ∈ p, ϕ(o).
Thus, it is clear that inference rules that hold for "everywhere", not necessarily hold for "somewhere". Indeed, the rule 2.2 (ϕ, p), (ψ, p) (ϕ∧ψ, p) is no longer valid since ∃o ∈ p, ϕ(o) and ∃o ∈ p, ψ(o ) doesn't entail ∃o ∈ p, ϕ(o ) ∧ ψ(o ). More generally, here are the rules that hold for the "somewhere" reading:
Proposition 5 (inference rules on attributive formulas). 1'. (¬ϕ ∨ ϕ , p ∧ p , e), (ϕ ∨ ϕ , p , s) (ϕ ∨ ϕ , p ∧ p , s) 2'. (ϕ, p, s), (ϕ , p, e) (ϕ ∧ ϕ , p, s); 3'. (ϕ, p, s), (ϕ, p , s) (ϕ, p ∨ p , s) 4'. if p p then (ϕ, p, s) (ϕ, p , s); 5'. if ϕ ϕ then (ϕ, p, s) (ϕ , p, s)
where (ϕ, p, s) stands ∀p , p p ∃o ∈ p , ϕ(o), and (ϕ, p, e) for ∀o ∈ p, ϕ(o). Moreover, between "somewhere" and "everywhere" formulas, we have: 6'. ¬(ϕ, p,s) ≡ (¬ϕ, p,e)
Taxonomy information and attributive information should be handled separately, because they refer to different types of information, and, more importantly, because taxonomy distinctions expressed by mutual exclusiveness of taxons do not mean that they cannot be simultaneously true in a given area: the taxonomy-formula (a ↔ ¬b), with a, b ∈ V i coming from the same taxonomy, differs from the attributive-formula (a ↔ ¬b, ), applied to every parcel (with the everywhere reading), since it may happen that for a parcel p, we have (a, p)∧(b, p) (with a somewhere reading). The latter may mean that p contains at least two distinct parts, and that ∃o ∈ p, ϕ(o) ∧ ∃o ∈ p, ψ(o ).
However, subsumption properties can be added to attributive formulas without any problem. Indeed ϕ ψ means ∀o, ϕ(o) → ψ(o), and if we have (ϕ, p), implicitly meaning that ∃o ∈ p, ϕ(o), then we obtain ∃o ∈ p, ψ(o), i.e., (ψ, p). Thus we can write the subsumption property as (ϕ → ψ, ).
Fusing consistent knowledge bases merely amounts to apply logical inference to the union of the knowledge bases. In presence of inconsistency, another combination process should be defined and used.
Possibilistic information fusion easily extends to attributive formulas: each given (ϕ, p) is equivalent to the conjunction of the (ϕ, p i ), on the leaves of the partonomy, such that p i |= p. We can always refine two finite partonomies by taking the non-empty intersection of pairs of leaves, and possibilistic fusion takes place for each p i . Clearly, we have four possible logical readings of two labels a and b associated with an area covered by two elementary parcels p 1 and p 2 :
i. (a ∧ b, p
When a and b are mutually exclusive the everywhere meaning is impossible (if we admit that sources provide consistent information).
Another ambiguity is about if the "closed world assumption" (CWA) holds, e.g.: if a source says that p i contains Conifer and Agriculture, does it exclude that p i would also contain Marsh ? It would be indeed excluded under CWA. Also, CWA may help to induce "everywhere" from "somewhere" information. Indeed, if we know that all formulas attached to p are ϕ 1 , . . . ϕ n with a somewhere meaning: (ϕ 1 , p, s) ∧ . . . ∧ (ϕ n , p, s)), then CWA entails that if there were another ψ that holds somewhere in p, it would have been already said, hence we can jump to the conclusion that ( i=1,n ϕ i , p, e).
Our logical framework also allows a possibilistic handling of uncertainty, and then a variety of combination operations, which may depend on the level of conflict between the sources, or on their relative priority [2], can be encoded.
After having identified representational needs (references to ontologies, uncertainty) when dealing with spatial information and restating ontology alignement procedures, a general logical setting has been proposed. This setting offers a non-ambiguous representation, propagates uncertainty in a possibilistic manner, and provides also the basis for handling multiple source information fusion.
As discussed along the paper, the handling of spatial information raises general problems, such as the representation of uncertainty or the use of the closed world assumption, as well as specific spatial problems. A particular representation issue is related to the need of "localizing" properties. First, this requires the use of two vocabularies referring respectively to parcels and to properties. Moreover, we have seen that it is often important to explicitly distinguish between the cases where a property holds everywhere or somewhere into a parcel: we have detailed this for fusion purpose, it may be present also when learning the taxonomy alignment (further research).