Armen Inants Armen Inants 11 2 2 bronze badges. Sign up or log in Sign up using Google. Sign up using Facebook. Sign up using Email and Password. Post as a guest Name. Email Required, but never shown. Featured on Meta. Tag synonym dashboard 2. We're testing advertisements across the network. Should we burninate the [ebay] tag? Linked 2. Related 0. Mark et al. Especially, the grouping task seems to be one prominent empirical method that is easy to carry out and to communicate to the participant. The basic idea is that the conceptualization of space guides the grouping of items into categories.
Subsequent intensional descriptions of the groupings may provide additional hints 1 what informational content was used by the subject to group the items, and 2 to lower the risk of choosing the wrong intension of extension-equivalent categories. For this investigation we start with very simple regions, namely, circles that can be related in only a limited number of ways. If it turns out that topological relations are important for grouping these simple regions, we can extend our investigation and use more complex regions. Otherwise, topological relations would not seem to be interesting from a cognitive point of view.
Figure 5. After solving some practice trials to get acquainted with the procedure they then saw the color screen as depicted in Figure 5. The 96 items of spatial 54 5. Subjects had to move the pictures on the left into groups at the right side of the screen. All subjects had to judge the same items because the aggregation of data had to be done across subjects per item. Instances for each relation were generated by a program that produced instances of the RCC-8 relations randomly with respect to metrical and ordering information.
In Table 5. Table 5. The size information used in the verbalizations was purely qualitative. This is a relevant point in our results because one important task in qualitative spatial reasoning is to extend topological calculi for other nontopological concepts like distance, direction, or size aspects.
If one wants to make this extension in such a way that the resulting calculi can still be called cognitively adequate, our empirical results provide useful hints in which direction to extend topological calculi. However, further evidence in particular investigations with more complex regions than circles will be needed before RCC-8 can be claimed as cognitively adequate.
Cognitive Properties of Topological Spatial Relations squares, pentagons or hexagons. Note Fig. This is only for increasing readability. We generated regular polygons with four to eight corners, and made sure that for each possibility of how two regions can connect each other there were at least some items. After solving some practice trials to get acquainted with the procedure subjects saw the color screen as depicted in Figure 5.
The left section contained the items and the right section the groupings subjects had to form. The items had to be moved with a mouse from the left to the right. In order not to bias the number of groupings, in the beginning only one group was displayed on the right, and subjects had the possibility to add as many groupings as they wanted. After the grouping phase, subjects had to describe their groupings by natural language descriptions in German.
For each subject the complete procedure 5. As it can be seen in the dendrogram of Figure 5. Dendrogram of the cluster analysis of items of the second investigation based on Hamming distances between items. For the EC items there are two sub-clusters of items with line contact and one-point contact 5. The clustering of groups on a higher level of the cluster analysis is due to idiosyncratic categorizations or mis-groupings of single items by a few subjects one subject wrote that he used one group as a clipboard and forgot to assign these items in the end.
Additionally, we introduced two new categories for the degree of contact of the boundaries C and mentioning of pure shape. Size and orientational information was only used in combination with topological information. Cognitive Properties of Topological Spatial Relations the objects, i.
Except for one subject, all others grouped the items according to the distinctions made by the RCC-8 relations. This result gives further evidence that topological relations in general are an important part of human spatial cognition, and that the level of granularity given by the RCC-8 relations is particularly important. Topological distinctions on a coarser level of granularity do not seem to be cognitively adequate.
These distinctions can all be made on a purely topological level without taking into account other spatial aspects such as direction, distance, or shape. Thus, it appears that topological relationships are much more important in human spatial cognition than any other relationships between spatial regions. As already explained, this is due to disregarding the relationship of a reference object with a to-be-localized object.
We believe that when this distinction is explicitly emphasized in the instructions, subjects will group items accordingly. In many cases this relies only on the researchers intuition.
SparQ - University of Bamberg
Whether or not a formal approach to spatial relations is a cognitively adequate model of human spatial knowledge is in fact an empirical question and can be answered only on the basis of empirical results. Both investigations reported above suggest that topological relations are an important part of human spatial knowledge. With a high level of agreement 64 5. In both investigations the distinctions made by the RCC-8 relations were the most important ones, which gives clear evidences of the cognitive adequacy of the RCC-8 relations. Relations on a coarser level of granularity such as the RCC-5 relations did not appear to be adequate.
From a cognitive point of view, these results give additional motivation for studying the RCC-8 relations. Future work on cognitive adequacy of topological relations includes further lifting the restrictions on the shape of the presented regions. One question is whether subjects continue to distinguish the number of connections and up to which number.
In our investigation some subjects distinguished between connections at a single point, at two points, and at a line. It will be interesting to see whether subjects distinguish connections at 1, 2, 3,. For arbitrary shapes of regions it is also possible that two regions connect at two or more lines. Another interesting question is how subjects group items when regions are allowed to consist of multiple pieces or to have holes. So far we have only investigated conceptual cognitive adequacy of systems of topological relations.
It will be interesting to see how humans reason about these relations, and to investigate the inferential cognitive adequacy of the reasoning methods used in qualitative spatial reasoning cf. Computational Properties of RCC-8 In the previous chapter we found evidence that topological relations in general and RCC-8 in particular are a fundamental part of human conceptualization of space. Those relations that are transformed to propositional Horn formulas, which is a tractable fragment of SAT, form a tractable subset of RCC This is important since the path-consistency method is consistency of H very simple and runs in time O n3.
All three decision problems are NP-hard . In order to assure the correct assignment of positive and negative literal occurrences with respect to the corresponding variable, polarity constraints are required again. For instance, if the variable v is assigned true, i. Property 6. With Property 6. Using Property 6. Theorem 6. Depen- 6. With this transformation for every literal as well as for every literal occurrence two spatial variables x and y with the appropriate indices are introduced.
Transformation step 1 introduces the spatial variables corresponding to the positive and the negative literal of each variable. This is 70 6. Transformation step 2 introduces spatial variables for every literal occurrence. Again, Property 6. Finally, transformation step 3 together with Property 6. Because of 5 and 6 , the spatial variables can be divided into two sets.
The relation PO only holds between regions of the same set. This can be seen in Figure 6. In every clause there is either one small region which is proper part of another small region or a big region which is proper part of another big region. In Figure 6.
Also there is one small region in every clause that partially overlaps one big region. In M every spatial variable xi of the small set is instantiated by Si , every spatial variable xi of the big set is instantiated by Bi. Corollary 6.
In order to identify this borderline, one has to examine all subsets of RCC Additionally, we require the universal relation to be in the subset, so that it is possible to express complete ignorance. This reduces the number of subsets we have to analyze from to Instead of reproving this fact for the RCC-8 relations, we will prove a more general result.
Let C be a set of binary relations that is closed under composition, intersection, and converse. Let n be the maximal number of operations needed for a single element, where for each element the minimal number of operations is considered. Note that Theorem 6. Another requirement of Theorem 6. Otherwise the identity relation must be contained in S. Let S be a subset of RCC With the second statement of Corollary 6. The NP-hardness proof of Theorem 6. Lemma 6. Let S be a subset of RCC-8 containing all base relations.
Then Properties 6. Because of Property 6. As in Theorem 6. If Xi is instantiated with Si then Yi is instantiated with Bi and vice versa. It can 6. In every clause there are two exceptions, namely, that one big region is tangential proper part of another big region and one small region partially overlaps one big region. Then all 76 6. A model for the six regions in Figure 6. With Corollary 6. By computing the closure of all sets containing the eight base relations together with one additional relation, we obtain the following lemma.
Using the modal encoding of RCC-8 given in Section 4. It results from the regularity constraint 4. Instead of 4. Computational Properties of RCC-8 The modal encoding of spatial constraints containing only base relations results directly from Table 4. In order to make the following application of these steps more readable, we will introduce some abbreviations for the model and entailment constraints and for the regularity constraints.
When it is obvious which atoms regions are used, the abbreviations will be written without indices. The abbreviated form of a relation R is the modal encoding m1 xRy of R for some spatial variables x and y written in abbreviated form. The truth conditions of these formulas can be obtained by combining the truth values of the single atoms.
We start with specifying the truth conditions of the model constraints.
Qualitative Spatial Reasoning with Topological Information
For this we will successively add only those worlds to the frame that are explicitly required by the formulas 6. If a world with these properties is not present, it has to be introduced. These properties must be enforced by the model and not by the frame. For this we will classify worlds according to the accessibility relation RI holding between them. Every occurrence of one of the formulas 6. Formulas 6. Every model shall be designed according to these principles.
W contains only worlds up to level l, i. Note that item 4 guarantees that every RCCframe of level l is an S4frame. As there are n regions and therefore n2 relations, there are at most 6n2 worlds of level 0. It might be decreased by optimizing the abbreviated form with respect to the number of negated abbreviations.
Trivially, if the formulas 6. The same for the formulas 6. As the only RI -successor of a world of level 1 is the world itself, formulas 6. So only formula 6. Suppose that formula 6. Then 6. If the atom is forced by one of the formulas 6. We have constructed a polynomial RCCmodel of level 1 which contradicts our initial assumption that there is no such model.
It follows from Theorem 6. As stated before, the entailment constraints, i. Since in the RCCmodel every world of level 1 has 2n RI -successors, we will reserve one of these 2n RI -successors for every statement of this kind. The transformation is given in the following proposition. Proposition 6. This increases the size of the resulting propositional formulas only polynomially. For the model constraints and for the constraint CP, p is equal to q.
From Lemma 6. Together with Corollary 6. Computational Properties of RCC-8 6. In our framework some disjunctions of model and entailment constraints are tautologies. These disjunctions of abbreviations can be eliminated from the abbreviated form. We prove that the above given modal formulas are tautologies by showing that the negation of each of these formulas results in a contradiction.
This can be done by using, e. All relations with an abbreviated form using only abbreviations or disjunctions of abbreviations transformable to Horn formulas can be transformed to Horn formulas. In this way 64 relations can be transformed to Horn formulas. They are listed in Appendix A. We call the subset of RCC-8 containing these relations H8. Every constraint using a relation of H8 is transformable to a Horn formula. With this transformation for every variable as well as for every literal occurrence two spatial variables x and y with the appropriate indices are introduced.
The polarity constraints assure that both literals have complementary assignments see Figure 6. Again, the polarity constraints assure correct assignments. Finally, transformation step 3 makes sure that at least one literal occurrence of every clause is true. All other combinations are possible. We now have to show that an instance of 3SAT 92 6. For every literal and every literal occurrence that is assigned f alse, the corresponding spatial variables hold the relation EQ and can therefore be treated as a single spatial variable.
Figure 6. All regions corresponding to the literal occurrences of a clause ci are placed within the region Ci. Spatial variables corresponding to the variables P and Q and to their literal occurrences is contained in Ci if a literal occurrence of the variable is contained in ci. All regions within region Ci can be arranged consistently in a way that all required relations hold. H As it has not been proven that adding relations of N3 to the base relations results in intractability of RSAT, there might be other maximal tractable subsets of RCC-8 containing all base relations.
We will call this subset H5. Computational Properties of RCC-8 The following lemma can easily be obtained by computing the closure of the employed sets. H all base relations. To prove NP-hardness Proof. The previously mentioned path-consistency method see Section 2. Positive unit resolution PUR is a resolution strategy in which in every resolution step at least one of the two resolved clauses is a positive unit clause, i. Since the Horn formulas that are 6. In this subsection we will show how unit clauses can be derived, and how this relates to the structure of the initial set of constraints.
RK x, y means that the relation between x and y is one of RK. According to Proposition 6. Then A has a minimal element m, i. Then P m also holds, which contradicts the assumption. So A must be empty, i. Suppose that S is the chain structure of a constraint xRy and the same constraint is contained in S. Let R be a relation of RCC We will prove P S with Noetherian induction. The two clauses cannot be obtained by c CP because in this case they cannot have the same index i. Because of item 2 of Proposition 6. Because of items 3 and 6 of Proposition 6.
With the operations of Proposition 6. By Noetherian induction we proved that P S holds for all chain structures S. The six possible cases of the proof to Lemma 6.
- Spatial–temporal reasoning!
- Similar books and articles.
- WHY YOU SHOULD NOT GO TO LAW SCHOOL!
- Qualitative Spatial Reasoning with Topological Information - PDF Free Download.
- The Power of Balance;
- Research on Cognitive Domain in Geoscience Courses: Temporal and Spatial Reasoning (Cog A).
In the lower row x is equal to y with the path-consistency method. Using this lemma, we can now prove that the path-consistency method decides RSAT H8 by showing that whenever the empty clause can be derived, the path-consistency method results in an inconsistency.
Then, with Proposition 6. Because of Lemma 6. As it was shown in the six cases of Lemma 6. In order to obposition 6. Thus, whenever PUR derives the empty clause, an inconsistency is found by the path-consistency method. H Proposition 6. Add R to S. Some relations of H so these relations can also be used to derive positive unit clauses. As all of 6. In Appendix A. We have chosen a construction of all relations such that the following analysis is as simple as possible. The set of relations that can be used to derive the empty clause will be denoted by Re. Analogous to Lemma 6. Similar to Lemma 6.
We will prove P T by Noetherian induction. This is again a contradiction to our assumption. Both possibilities result in a contradiction to previous assumptions. The same proof as in Theorem 6. This theorem can be easily transfered to RCC RMIN H 6. As in the case of qualitative temporal reasoning e.
Therefore it is not necessary to choose another label of the same constraint and, thus, the algorithm requires only time O n3. However, as it follows from Proposition 6. It follows from Lemma 6. In all of these cases it turns out mostly by applying Lemma 6. By Lemma 6. As it was shown in the proof of Lemma 6. Their abbreviated form is the following see Appendix A.
We will start with the four relations of a. Impose path-consistency after each of the steps 1 — 5. It times. Proof Sketch. However, by analyzing the composition table of the RCC-8 relations see Table 4. In many restrict the relations used in an application to the relations of H applications this is certainly not possible. Since the closure of these 16 relations is the whole set of RCC-8 relations, all relations have to be considered in this kind of applications. Supposing that the relations are uniformly distributed, the average branching factor, i.
This redurelations can only be expressed as a union of three H ces the average branching factor to 1. Both branching factors are of course worst-case measures because the search space can be considerably reduced when path-consistency is used as a forward checking method . Table 6.
In Chapter 8 we present an empirical study of reasoTable 6. Other complexity results on qualitative spatial reasoning were obtained by Grigni et al. These NP-hardness results are independent from our NP-hardness result. The notion of realizability is much more constraining than our notion of consistency. It is also computationally much harder — realizability for the eight base relations of RCC-8, e. Nebel  proved tractability for the set of RCC-8 base relations by transforming the propositional intuitionistic encoding of the base relations given by Bennett  to Krom formulas. This tractability result, however, is not applicable in our case, since Nebel did not consider the regularity condition.
The regularity condition is necessary to rule out certain counterintuitive regions, as, e. Moreover, since we are restricting our analysis to closed regions, the regularity condition is required in order to guarantee inferences according to the RCC-8 composition table. Consider, e. In this case, since B intersects A and C but the interior of B does not intersect A and C, B is externally connected to both A and C, which is not consistent with the composition table. Apart from H containing all base relations, they discovered three other tractable subclasses not containing all base relations.
However, in the following chapter we will make a complete analysis of tractability by identifying all maximal tractable subclasses of RCC-8 that contain all base relations. It is, however, not clear whether H or whether there are other maximal tractable subsets of RCC-8 that contain all base relations. There are at least two reasons why answering this question is important. First of all, without a complete analysis of tractability there are interesting subsets of RCC-8 for which it is unknown whether reasoning over these sets is tractable or NP-complete.
In this chapter we will give a complete analysis of tractability in RCC Since only tractable subsets containing all base relations can be used to speed up backtracking algorithms for the full set of RCC-8 relations, we restrict our analysis to those subsets that contain all base relations.
This way of proving tractability requires very detailed semantical knowledge about the considered set of relations and a suitable reduction to a tractable decision problem. The method is simple, since it does not require other semantical knowledge about the relations than given by the composition table.
A prerequisite of this method is a known tractable set for which path-consistency decides consistency. We propose the algorithm Check-Refinements see Figure 7. Suppose that we start with the triple x1 , x2 , x3. Lemma 7. Theorem 7. From Theorem 7. For RCC-8 it will help us to make a complete analysis of tractability by identifying two large new maximal tractable subsets. Then, a tractable subset is maximal tractable if any superset is NP-hard. In this section we present new NP-hardness results for RCC-8 and identify those subsets that are candidates for maximal tractable subsets, i.
This result rules out a lot of subsets of RCC-8 from being tractable, but still leaves the problem of tractability open for a large number of subsets. The additional NP-hardness results are shown in the following two lemmata.
They are proven by reducing 3SAT to the respective consistency problem. N P 8 contains 76 relations, P8 contains relations. Combining Lemma 6. Corollary 7. We computed all subsets of P8 that are candidates for maximal tractable subsets with respect to the above two NP-hardness proofs, i. The other two subsets are denoted by C8 and H Q8. So far we have not said anything about the tractability of C8 or Q8 or subsets thereof. However, we will see in the next section that both C8 and Q8 are in fact tractable. Proposition 7.
Conjecture 7. If we can prove this conjecture, then, by Proposition 7. In Section 6. Instead, we can now apply our new method developed in Section 7. It follows from Proposition 7. By applying the method developed in Section 7. According to Theorem 6. For this 7. This was computed in less than 25 minutes on a Sun Sparc Ultra1. We can now apply Theorem 7. We applied 7. Our new method is very simple, does not require detailed knowledge about the considered relations, and seems to be very powerful.
This leads to an interesting question, namely, whether it is a general property of sets of relations containing all base relations for which path-consistency decides consistency that the identity relation can be eliminated from all constraints of a pathconsistent set without making the set inconsistent.
For these candidates, Check-Refinements immediately returned fail. These sets can be used to speed up backtracking search for the general NPcomplete reasoning problem by reducing the search space considerably see Table 6. Nevertheless, the search space is still exponential in the size of the problem instance and it cannot be expected that it is possible to solve large instances in reasonable time.
In this chapter we tackle several questions that emerge from the results of the previous chapters. Up to which size is it possible to solve instances in reasonable time? Which heuristic is the best? This was the case for similar temporal problems pointisable vs. ORD-Horn relations . In doing so, we are particularly interested in the hardest randomly generated instances which leads to the question of phase-transitions : Is there a parameter for randomly generating instances of the consistency problem of RCC-8 that results in a phase-transition behavior?
If so, is it the case that the hardest instances are mainly located in the phase-transition region while the instances not contained in the phasetransition region are easily solvable? On the one hand instances which contain constraints over all RCC-8 relations, on the other hand instances which contain only constraints over relations which are not contained in any of the maximal tractable subsets.
We expect these instances to be harder on average than the former instances. Therefore we randomly generated our test instances with a given number of regions n, an average label-size l, and an average degree d of the constraint graph. Based on these sets of relations, we used two models to generate instances, denoted by A n, d, l and H n, d, l. The former model uses all relations to generate instances, the latter only the relations in N P 8.
The instances are generated as follows: 1. A constraint graph with n nodes and an average degree of d for each node is generated. Otherwise a non-universal relation is selected according to the parameter l such that the average size of relations for selected edges is l. Otherwise we repeat the process. Achlioptas et al. However, since the probability of getting the universal relation is very low, we ignore this in the following.
Ternary constraints over these variables are imposed by the composition table, i. Since one locally inconsistent triple makes the whole instance inconsistent, we are interested in the average degree d for which n the expected number EIT of locally inconsistent triples is equal to one. For the model H n, d, l , none of the possible assignments of the triples leads to a local inconsistency, i. In order to solve the randomly generated instances of RSAT, we used the backtracking algorithm of Figure 2. This is, of course, a worst case measure because the interleaved path-consistency computations reduce the branching factor considerably .
In general it is the best search strategy to proceed with the constraint with the most constraining relation line 3 of Figure 2. Restrictiveness of a relation is a measure of how a relation restricts its neighborhood. For instance, the universal relation given in a constraint network does not restrict its neighboring relations at all, the result of the composition of any relation with the universal relation is the universal relation.
The identity relation, in contrast, restricts its neighborhood a lot. In every triple of variables where one relation is the identity relation, the other two relations must be equal. Therefore, the universal relation is usually the least restricting relation, while the identity relation is usually the most restricting relation.
Restrictiveness of relations is represented as a weight in the range of 1 to 16 assigned to every relation, where 1 is the value of the most and 16 the value of the least restricting relation. We discuss in the following section in detail how the restrictiveness and the weight of a relation is determined. Given the weights assigned to every relation, we compute decompositions and estimate constrainedness as follows.
If there is more than one possibility, we chose the decomposition with the least restricting sub-relations. In line 5 of the backtracking algorithm see Figure 2. We choose the constraint with the smallest decomposition larger than one and, if there is more than one such constraint, the one with the smallest weight.
For the global strategy, the constrainedness of a constraint xRy is determined by adding the weights of all neighboring relations S, T with xSz and zT y to the weight of R. For this reason, we ran all our run-time experiments on the same machine, a Sun Ultra 1 with MB of main memory. In contrast to this, the number of visited nodes for solving an instance with a particular heuristic is always the same on every machine. This allows one to compare the path through the search space taken by the single heuristics and to judge which heuristic makes the better choices on average.
However, this does not take into account the time that is needed to make a choice at a single node. Computing the local constrainedness of a constraint is certainly faster than computing its global constrainedness. Similarly, computing constrainedness statically should be faster than computing it dynamically. Furthermore, larger instances require more time at the nodes than smaller instances, be it for computing path-consistency or for computing the constrainedness. Taking running-time and the number of visited nodes together gives good indications of the quality of the heuristics.
Common challenges and misconceptions The scale of events in geologic time does not correspond with events on the human time scale Students are challenged by exponential numbers and orders of magnitude, two of the basic mathematical concepts that underlie the concept of deep time Timelines students encounter in other classes may be represented horizontally, while geoscientists tend to represent the timescale vertically, with the youngest at the top. Students' cultural or religious views may conflict with the scientific understanding of geologic time.
Show Connections to big ideas, essential principles, and fundamental concepts about time in the geoscience literacies. Connections to big ideas, essential principles, and fundamental concepts about temporal reasoning in the geoscience literacies Earth Science Big Idea 2. Earth is 4. Fundamental concept 2. Earth's rocks and other materials provide a record of its history. Over Earth's vast history, both gradual and catastrophic processes have produced enormous changes.
Earth Science Big Idea 3. Earth is a complex system of interacting rock, water, air, and life. Fundamental concept 3. Earth's systems interact over a wide range of temporal and spatial scales.