A. G. Cohn and S. M. Hazarika 1-29
The paper is a overview of the major qualitative spatial representation and reasoning techniques. We survey the main aspects of the representation of qualitative knowledge including ontological aspects, topology, distance, orientation and shape. We also consider qualitative spatial reasoning including reasoning about spatial change. Finally there is a discussion of theoretical results and a glimpse of future work. The paper is a revised and condensed version of [33, 34].
Ernest Davis 31-54
A natural approach to defining continuous change of shape is in terms of a metric that measures the difference between two regions. We consider four such metrics over regions: the Hausdorff distance, the dual-Hausdorff distance, the area of the symmetric difference, and the optimal-homeomorphism metric (a generalization of the Fréchet distance). Each of these gives a different criterion for continuous change. We establish qualitative properties of all of these; in particular, the continuity of basic functions such as union, intersection, set difference, area, distance, and smoothed circumference and the transition graph between RCC-8 relations. We also show that the history-based definition of continuity proposed by Muller is equivalent to continuity with respect to the Hausdorff distance.
Antony Galton 55-70
Dominance diagrams are an extension of the conceptual neighbourhood diagrams (CNDs) that have become familiar in the areas of qualitative spatial and temporal knowledge representation. They are also related to the envisionment diagrams of qualitative physics. This paper explains the concept of dominance between qualitative states and shows how, by adding a representation of this relation to CNDs, it is possible to reason more effectively about the temporal incidence of the qualitative states represented in the diagrams; in addition, dominance turns out to be of importance in determining the structure of composite diagrams formed as the product of existing diagrams. It is further shown that the appropriate theoretical underpinning for dominance diagrams is the mathematical theory of T0 topological spaces.
Ivo Düntsch, Ewa Or³owska and Hui Wang 71-82
Lech Polkowski 83-96
Rough mereology is a paradigm for reasoning under uncertainty whose primitive notion is that of being a part to a degree; hence, rough mereology falls in the province of mereology-based theories for reasoning about complex objects. Among mereological theories of objects, theories based on the primitive notion of a connection distinguish themselves by a variety of applications of which we would like to mention the area of Qualitative Spatial Reasoning. In this paper, we define rough mereologies within the realm of mereologies based on the primitive notion of a part and we show that in this framework one may induce notions of connection closely related to initial rough mereologies in the sense that they induce the same notion of a part. We also address the distributed environment proving some results about connection preservation throughout the reasoning system.
Thomas Bittner 97-128
This paper provides an ontological analysis of built environments. It shows that boundaries are ontologically salient features of built environments and that there are different kinds of boundaries that that need to be considered. It discusses in particular the important role of fiat boundaries. At the level of objects built environments are formed by partition forming objects and populated by non-partition forming objects. The underlying partition structure is the main organizational structure of a built environment. Non-partition forming objects are potentially movable and their movement is constrained by the barrier properties of the boundaries of other objects forming or populating the environment.
This paper argues that the qualitative formalization of built environments needs to take into account: (1) the fundamental role of boundaries, (2) the distinction between bona-fide and fiat boundaries and objects, (3) the different character of constraints on relations between these different kinds of boundaries and objects, (4) the distinction between partition forming and non-partition forming objects, and (5) the fundamental organizational structure of regional partitions. It discusses the notion of object-boundary sensitive rough location and shows that a formalization based on this notion takes these points into account.
Dominik J. Schoop 129-143
It is considered the virtue of mereotopology that it takes regions instead of points to be the primitive entities of space. As mereotopology is assumed to avoid the difficulties incurred by considering points as primitive entities, mereotopology is thought to provide the means for common-sense spatial representation and reasoning. However, we show that considering regions as primitive entities in mereotopology does not prevent us referring to points in a commonly used mereotopological first-order language. Therefore, the difficulties attributed to taking points as primitive entities must be considered even for point-free mereotopologies. Consequently, the virtue of mereotopology cannot lie in taking regions instead of points as primitive entities. On the contrary, we argue that the virtue of mereotopology is its capability to treat regions and points as primitive entities.
Brandon Bennett 145-158
Region Based Geometry (RBG) is an axiomatic theory of qualitative configurations of spatial regions. It is based on Tarski's Geometry of Solids, in which the parthood relation and the concept of sphere are taken as primitive. Whereas in Tarski's theory the combination of mereological and geometrical axioms involves set theory, in RBG the interface is achieved by purely 1st-order axioms. This means that the elementary sublanguage of RBG is extremely expressive, supporting inferences involving both mereological and geometrical concepts. Categoricity of the RBG axioms is proved: all models are isomorphic to a standard interpretation in terms of Cartesian spaces over \mathbbR.
Ian Pratt-Hartmann 159-186
Suppose we want to develop a theory of space in which the primary entities are not points, but regions. How do we proceed? Historically, the most popular approach is to select a group of spatial relations corresponding to familiar spatial concepts, and then to construct an axiomatic system governing these relations. The appropriateness of this axiomatic system is to be judged on the basis of its ability to chime with pre-theoretic intuition and of its success in a larger theory of scientific or commonsense spatial reasoning. In this paper, we argue that this approach is flawed, and leads only to labyrinthine systems of doubtful theoretical or practical value. We present an alternative approach which substitutes mathematical rigour for pre-theoretic intuition, and which at the same time provides a real guarantee of practical applicability.
Sergio A. Celani 187-197
We present a fragment of Propositional Dynamic Logic based on the Intuitionistic Propositional Logic. We show that this logic has the finite model property, and therefore, is frame-complete.
Churn-Jung Liau and Duen-Ren Liu 199-217
In this paper, we investigate a knowledge representation formalism in the context of fuzzy data tables. A possibilistic decision logic incorporating linguistic terms is proposed for representing and reasoning about knowledge in fuzzy data tables. Two applications based on the logic are described. The first is the extraction of fuzzy rules from general fuzzy data tables. In this application, the knowledge in the tables may be made explicit by the formulas of the logic or used implicitly in decision-making. The second is for the fuzzy quantization problem of precise data tables. It can be viewed as a special case of the first, however, due to some special properties of the problem, a polynomial time rule extraction process can be obtained. Finally, the relationship of the logic with some works for handling uncertain information in data tables is also discussed.
A.P. Engelbrecht 219-252
Research on improving the performance of feedforward neural networks has concentrated mostly on the optimal setting of initial weights and learning parameters, sophisticated optimization techniques, architecture optimization, and adaptive activation functions. An alternative approach is presented in this paper where the neural network dynamically selects training patterns from a candidate training set during training, using the network's current attained knowledge about the target concept. Sensitivity analysis of the neural network output with respect to small input perturbations is used to quantify the informativeness of candidate patterns. Only the most informative patterns, which are those patterns closest to decision boundaries, are selected for training. Experimental results show a significant reduction in the training set size, without negatively influencing generalization performance and convergence characteristics. This approach to selective learning is then compared to an alternative where informativeness is measured as the magnitude in prediction error.
Ferucio Lauren tiu Tiplea and Erkki Mäkinen 253-256
A synchronized extension system is a 4-tuple G = (V,L1,L2,S), where V is an alphabet and L1, L2 and S are languages over V. Such systems generate languages extending L1 by L2 to the left or to the right, and synchronizing on words in S.
In this note we consider the relationship between synchronized extension systems and regular canonical systems. We are able to give a simplified and generalized proof for the classical result concerning the regularity of the languages defined by regular canonical systems.
Rakesh M. Verma, Michael Rusinowitch and Denis Lugiez 257-276
In this paper we initiate a study of polynomial-time reductions for some basic decision problems of rewrite systems. We then give a polynomial-time algorithm for the unique-normal-form property of ground systems for the first time. Next we prove undecidability of several problems for a fixed string rewriting system using our reductions. Finally, we prove the decidability of confluence for commutative semi-thue systems. The Confluence and Unique-normal-form property are shown Expspace-hard for commutative semi-thue systems. We also show that there is a family of string rewrite systems for which the word problem is trivially decidable but confluence is undecidable, and we show a linear equational theory with decidable word problem but undecidable linear equational matching problem.
Radim Blohlávek 277-285
Presented is a reduction of fuzzy Galois connections and fuzzy
concept lattices to (crisp) Galois connections and concept
lattices: each fuzzy concept lattice can be viewed as a concept
lattice (in a natural way). As a result, a simple proof of the
characterization theorem for fuzzy concept lattices is obtained.
The reduction enables us to apply the results worked out for
concept lattices to fuzzy concept lattices.
Martin Dietzfelbinger, Anna Gambin and S³awomir Lasota 287-314
Multistage interconnection networks (MINs) have a number of
applications in many areas, for example in parallel computing
systems or high-speed communication networks. In the paper we
define Markov chains describing several models of packet flow
through the buffered MIN with a butterfly interconnection
structure and 2 ×2 switching elements. We develop a
notation together with a mathematical framework enabling to prove
certain results relating the models. Moreover, we show that all
considered Markov chains are ergodic and discuss relationships
between stationary distributions. The important novelty is that
our approach is compositional, which allows to keep the complexity
of description of a very complicated network's behaviour on a
reasonable and tractable level. Considerations are mostly
independent of specific network topology and routing protocol,
hence we expect our method to be applicable also in other contexts
for stochastic models of massively parallel systems.
Linh Anh Nguyen 315-342
We propose a modal query language called MDatalog. A rule of an
MDatalog program is a universally quantified modal Horn clause.
This language is interpreted in fixed-domain first-order modal
logics over signatures without functions. We give algorithms to
construct the least models for MDatalog programs. We show PTIME
complexity of computing queries for a given MDatalog program in
the logics KD, T, KB, KDB, B, K5, KD5, K45,
KD45, KB5, and S5, provided that the quantifier depths of
queries and the program are finitely bounded, and that the modal
depth of the program is finitely bounded in the case when the
considered logic is not an extension of K5. Some examples are
given to illustrate application of the techniques to reason about
belief and knowledge.
Jan Ostravský 343-348
In [9] submonoids of a commutative monoid are characterized by
means of their relations of domination, subgroups of a commutative
monoid are characterized by means of their relations of double
domination. The main purpose of this paper is to transfer these
results to general monoids. The important means will be certain
relations, which we shall study in detail.
Christian Ronse and Jean Serra 349-395This paper generalizes the notion of symmetrical neighbourhoods, which have been used to define connectivity in the case of sets, to the wider framework of complete lattices having a sup-generating family. Two versions (weak and strong) of the notion of a symmetrical dilation are introduced, and they are applied to the generation of ``connected components'' from the so-called ``geodesic dilations''. It turns out that any ``climbing'' ``weakly symmetrical'' extensive dilation induces a ``geodesic'' connectivity. When the lattice is the one of subsets of a metric space, the connectivities which are obtained in this way may coincide with the usual ones under some conditions, which are clarified. The abstract theory can be applied to grey-level and colour images, without any assumption of translation-invariance of operators.