John G. Stell
Department of Computer Science
Keele University
Keele, Staffs, ST5 5BG
U. K.
john@cs.keele.ac.uk
1: Why I want to participate
The underlying theme of my research over the last 15 years has been
theapplication of concepts from algebra and logic to modelling
computationalphenomena. In the last couple of years I have started to
concentrate onmodels within the area of spatial information theory and
GIS. Mathematicaldevelopments within the last 50 years, centring on the
rise of categorytheory, have led to some revolutionary new ways of
understanding and applyingmathematics. These modern developments have
considerable potential forapplication to theories of spatial information,
as I have already begunto demonstrate. At the most recent COSIT meeting
(Stell & Worboys,1997) I showed how the category-theoretic concepts of
`pointless topology'lead to a better understanding of the
Region-Connection Calculus. In apaper at the forthcoming SDH conference
(Stell & Worboys, 1998) sheaf-theoreticideas are used to organize a
formal account of multi-resolution spatialdatabases.
This workshop seems an ideal occasion to see if three particular issuesin
the modelling of perception, cognition and change can be developed
further.Two features of sheaf theory suggest that it is relevant to this
workshop.These features are its ability to handle variation over time and
space,and to handle the relationships between local and global aspects of
dynamicphenomena. I have also been considering Poston's work on fuzzy
spaces (toavoid misunderstanding, it is worth noting that this makes no
use of themore widely known `fuzzy set theory'). Fuzzy spaces arose in the
contextof perception, and are claimed to model perceived space much better
thanconventional mathematical models. Very little work on these spaces
hasbeen carried out since Poston's in the early 1970s, but there is
clearevidence that they deserve further investigation. The third issue I
wouldlike to see discussed concerns the semantics of identity.
Overall, I believe that I could contribute a knowledge of a rangeof
mathematical concepts, particularly in the area of category theory,which
are relevant to the workshop. However, it is all too easy to
proposemathematically motivated models from a superficial acquaintance
with thesubject matter of the models. Thus the opportunity to have
discussionswith experts in the psychological and geographical aspects of
the subjectwould be valuable for the development of my own work.
2: Position Statement
The need for formalism
Formal models, using mathematical concepts, are applicable to the
concernsof the workshop for a number of reasons. These models are
important ifwe take a computer science viewpoint and consider the
construction of GISwhich take account of cognitive models. As an example,
take the issue ofstructure in cognitive maps. Hirtle (1995) considers
hierarchical structuresfor spatial memory, and shows that the use of
ordered trees or semi-latticescan be more appropriate than strictly
hierarchical trees. If we want toimplement GIS in a way consistent with a
user's internal cognitive map,concepts such as ordered trees or
semi-lattices can be used to structurethe overall design of the system.
Formal models are also relevant to thegeographical and the psychological
viewpoints. The use of formalisms whenbuilding cognitive models of dynamic
phenomena allows us to understandrelationships between a variety of
proposed models, and to assess the relativemerits of different models.
Aspects of Change
There are several relatively recent developments in mathematics which
canplay a role in modelling cognitive aspects of change. Rather than
attemptto catalogue everything which might be useful, I want to consider
threetopics. To understand how these topics relate to each other, and to
thenotion of change itself, I will first consider three aspects which
areoften present when dealing with phenomena of change.
The development of a city over an historical period provides a
simpleillustration. Concentrating on the region of space occupied by the
city,we can isolate three aspects:
- A domain over which change occurs (in this case time)
- A property which varies (in this case the regional location)
- An underlying entity which has continued identity throughout the
changes(in this case the city).
It is important to realize that the domain of variation need not be
time,but could equally well be space, or space-time, or something else.
Forinstance, consider a GIS capable of displaying maps of a given region
atvarious levels of detail. A user of such a system can think of what
isprovided as a single map (the underlying entity) which has an
appearancewhich varies over a domain of levels of detail.
The three aspects identified are fundamental to modelling phenomenaof
change. Together they raise some important issues which should be
amongthose addressed by the workshop. Before elaborating on these specific
issues,I want to consider a branch of mathematics which has provided some
significantinsights into some of these issues.
Category Theory and its application to Cognition
The classical mathematical tools of set theory are well known and
widelyused in formal approaches to computer science, philosophy, cognitive
science,artificial intelligence etc. These tools can be very effective,
but havesome serious limitations. For example, Smith (1995) concludes that
"Set-theoreticstructure provides no basis for an understanding of the
many and variedsorts of genuine unification (causal, biological,
psychological, artefactual,institutional) by which the common-sense world
is structured."
Category theory provides an alternative approach to mathematics whichhas
much to offer those working in areas related to the topic of this
workshop.A category in the mathematical sense is a particular algebraic
structure,essentially a directed graph equipped with the ability to
compose edges.The notion of category was formulated in 1945, and since
then categorytheory has been used, among other things, as a way of
organizing and understandingmathematics itself. It may well be that the
success of category theorycan be explained in terms of Lakoff and Nunez'
(1997) metaphorical accountof mathematics. One of the appealing aspects of
category theory is itsuse of diagrams (originating from the underlying
graphs). The use of arrowsappears to exemplify Lakoff's
source-path-goal schema, which isalso important in the cartographic
context (MacEachren 1995, p189).
There have been very few applications of category theory in a
specificallyGIS context, but there is clear evidence that further
investigation wouldbe worthwhile. Ehresmann & Vanbremeersch (1987) use
category theoryto model the emergence of properties within complex
systems. Hoffman (1985)applies category theory to perceptual and cognitive
systems. A particularway in which category theory may be important in
modelling change is notedby Magnan & Reyes (1994, p58). They observe
that the objects referredto in natural languages "are ephemeral and
changing, unlike numbersand sets which are timeless and constant. Category
theory gives us themeans to define a generalized (...) set as an object of
a category satisfyingsome properties (a topos), without the temptation to
go into overdeterminations..."
Local and Global aspects of Variation over a Domain
In observing some changing geographical phenomenon over a period of
time,how are individual observations over small time periods constructed
intoa model of the phenomenon over its entire lifetime? In learning a new
environment,how do humans build up a global cognitive map from individual
episodesof interaction with the environment? Both these questions have
been thesubjects of several studies, for an example of the latter one
there isthe combination of `local maps' and of `regional maps' in
Chown,Kaplan & Kortenkamp (1995). The category-theoretic tools of
sheaf theoryare likely to helpful in providing a formal framework for
dealing suchquestions, but their application to this area has not yet been
exploredin any detail.
Sheaf theory allows us to model `local' properties of structures, andtheir
relationship to `global' properties. The notion of local
versus global can be interpreted temporally (small portions of time
within a largerinterval), or spatially (small subregions within a larger
region). It canalso be understood in the context of variation over levels
of detail. Sheaftheory has been applied (Sofronie-Stokkermans 1997) to
modelling cooperatingsystems. One specific issue studied is how local
plans, made by individualagents, can be combined to realize some global
objective. It would be worthwhileto investigate whether the same
mathematical concepts can applied to provideuseful formal models in the
GIS context, for example handling the combinationof local (in any of the
senses indicated above) observations into globalones. It appears possible
that the Geocognostic framework (Edwards 1997)might be formalized as
sheaves over a space of trajectories. Such an approachwould be one way to
investigate formal models of cognitive maps of changingenvironments.
Indistinguishability in Perceived Properties.
Arbitrarily fine distinctions are not possible in our perception of
space.Even with the best conceivable instruments, there will point
locationswhich we cannot distinguish, but of which we cannot be certain
that theyare distinct. This applies to any aspect of perception, for
example colour,distance, sound etc. it applies just as much to spatial
regions as to points.However, classical mathematical models of space fail
to take account ofthis. We need to have a formal model in which we can say
that entitiesP and Q are indistinguishable, and Q and
Rare indistinguishable, while allowing the possibility that
P andR are distinguishable. Thus the relation of
indistinguishabilityis radically different from equality as it need not be
transitive. Thestudy of space in this sense was suggested by Poincare
(1913), and wasdeveloped in more detail by Poston (1971), but much remains
to be done.Varying the indistinguishably relation could be significant for
understandinggeneralization in the context of dynamic visualization, which
is acknowledgedto be an important research topic (MacEachren et al.
1998).
Identity of the Underlying Entity
We speak of the same forest at two different times even when none of
thetrees remain the same, and when the physical boundaries are
drasticallyaltered. Similarly we think of cities as having continuous
existence eventhough little besides the rough location of the settlement
is identifiableas constant over a period of centuries. Yet mere
preservation of locationdoes not always mean that we would talk of "the
same city". Thenotion of continuation of identity is central the
notion of change, yethas long been a source of philosophical problems
(Gallois 1998). Theseproblems are of practical relevance to any formal
account of GIS technologywhich is capable of dealing with change, and with
how we customarily thinkand talk about change. One example where some of
these ideas appear isin the change description language developed by
Hornsby and Egenhofer (1997).
A significant approach to the semantics of identity has been proposedby
Reyes, Macnamara and Reyes (1994). They develop a theory of
referenceapplicable to certain linguistic entities, including proper names
and countnouns. Some key elements of their treatment, including the
notions of entityand of coincidence between members of different kinds,
relies in an essentialway on the tools provided by category theory. Their
work is in a purelylinguistic context, but offers considerable promise for
application toentities in geographic space.
References
- Chown, E., Kaplan, S. & Kortenkamp, E. (1995)
- Prototypes, Location, and Associative Networks (PLAN):Towards a Unified Theory of Cognitive Mapping.
Cognitive Science 19(pp1-51).
- Edwards, G. (1997)
- Geocognostics - A New Framework for Spatial InformationTheory.
In Hirtle & Frank (1997) (pp455-471)
- Ehresmann, A. C. & Vanbremeersch, J.-P. (1987)
- Hierarchical Evolutive Systems: A Mathematical Model forComplex Systems.
Bulletin of Mathematical Biology 49 (pp13-50)
- Gallois, A. (1998)
- Occasions of Identity: A Study in the Metaphysics of Persistence,Change, and Sameness
Clarendon Press, Oxford.
- Hirtle, S. C. (1995)
- Representational Structures for Cognitive Spaces: Trees,Ordered Trees and Semi-lattices.
In A. U. Frank & W. Kuhn (Eds)Spatial Information Theory: A Theoretical Basis for GIS. Proceedingsof COSIT 95. Lecture Notes in Computer Science, vol 988 (pp327-340)Springer-Verlag, Berlin.
- Hirtle, S. C. & Frank, A. U. (Editors) (1997)
- Spatial Information Theory: A Theoretical Basis for GIS.Proceedings of COSIT 97.
Lecture Notes in Computer Science, vol 1329 Springer-Verlag, Berlin.
- Hoffman, W. C. (1985)
- Some Reasons why algebraic topology is important in neuropsychology:perceptual and cognitive systems as fibrations.
Int. J. Man-MachineStudies 22 (pp613-650)
- Hornsby, K. & Egenhofer, M. J. (1997)
- Qualitative Representation of Change.
In Hirtle &Frank (1997) (pp15-33)
- Lakoff, G. & Nunez, R. E. (1997)
- The Metaphorical Structure of Mathematics: Sketching OutCognitive Foundations for a Mind-Based Mathematics.
InL. D. English (ed.) Mathematical Reasoning: Analogies, Metaphors, andImages. Lawrence Erlbaum Associates.
- Magnan, F. & Reyes, G. E. (1994)
- Category Theory as a Conceptual Tool in the Study of Cognition.
In J. Macnamara & G. E. Reyes (Eds) The Logical Foundations of Cognition.(pp57-90) Oxford University Press, New York.
- MacEachren, A. M. (1995)
- How Maps Work: Representation, Visualization, and Design.
The Guildford Press, New York.
- MacEachren, A. M. & the ICA Commission on Visualization(1998)
- Visualization - Cartography for the 21st Century.
InProceedings of the Polish Spatial Information Association Conference, May1998, Warsaw, Poland.
http://www.geog.psu.edu/ica/icavis/ICAvis_working(1).html
Poston, T. (1971)
Fuzzy Geometry. Ph.D. Thesis, University of Warwick.
Poincare, H. (1913)
The Value of Science. Translated by G. B. Halsted.Dover Publications, New York (1958). Original French edition 1913.
Reyes, M. La P., Macnamara, J. & Reyes, G. E. (1994)
Reference, Kinds and Predicates. In J. Macnamara &G. E. Reyes (Eds) The Logical Foundations of Cognition. (pp91-143)Oxford University Press, New York.
Smith, B. (1995)
Formal Ontology, Common Sense and Cognitive Science.International Journal of Human-Computer Studies. vol 43 (pp641-667)
Sofronie-Stokkermans, V. (1997)
Fibered Structures and Applications to Automated TheoremProving in Certain Classes of Finitely-Valued Logics and to Modeling InteractingSystems. Ph.D. Thesis, Johannes Kepler Universitat,Linz, Austria. http://www.mpi-sb.mpg.de/~sofronie/research.html
3: Brief Curriculum Vitae
John Stell is a lecturer in the Department of Computer Science at
KeeleUniversity, in England. He has been a lecturer at Keele since 1988,
originallyjointly between the separate departments of Mathematics and of
ComputerScience. In 1997 he transferred to a position in Computer Science
in orderto concentrate his research activities on the theoretical
foundations ofGIS.
He studied mathematics (B.Sc. 1980) and computer science (M.Sc. 1981)at
the University of Manchester. From 1981 to 1985 he worked as a
researchassistant at Strathclyde University in Glasgow on various
projects, includingone on a diagnostic system for the logic programming
language Prolog. Thisproject (Coombs, Hartley and Stell, 1986) involved
the development andimplementation of a cognitive model to represent a
naive user's understandingof the Prolog interpreter.
After developing an interest in the mathematical concepts of
categorytheory and its applications to computer science, he returned to
Manchester(1985 - 1988) and obtained a Ph.D. in this area of theoretical
computerscience. He has a number of publications in the application of
category-theoreticmodels to term rewriting systems. This rather technical
work has provideda good background in a variety of mathematical concepts
which he is nowseeking to apply in the general area of spatial information
theory.
Selected Publications
M. J. Coombs, R. T. Hartley and J. G. Stell, (1986) Debugging User
Conceptionsof Interpretation Processes, AAAI-86 vol 1
pp303--307, AmericanAssociation for Artificial Intelligence.
J. G. Stell and M. F. Worboys, (1995) Towards a representation
forspatial objects in diverse Geometries, Proceedings of the Second
ACMWorkshop on Advances in Geographic Information Systems, pp38--43, ACM
Press,New York.
J. G. Stell and M. F. Worboys, (1997) The Algebraic Structure ofSets of
Regions, Spatial Information Theory, COSIT'97, S. C. Hirtleand A. U.
Frank (eds) Lecture Notes in Computer Science, vol 1329,
pp163--174,Springer-Verlag.
J. G. Stell and M. F. Worboys, (1998) Stratified map
Spaces:A Formal Basis for Multi-resolution Spatial Databases,
Proceedingsof International Symposium on Spatial Data
Handling, SDH'98.
J. G. Stell and T. Bittner, (1998) A Boundary-Sensitive Approachto
Qualitative Location, Annals of Mathematics and Artificial
Intelligence,Accepted for publication.
This page is currently maintained by Varenius Workshop Webmaster
Last Updated: Sep. 29, 1998