# Professor Sanjiang Li

**Core Member**, Joint Research Centre in Intelligent Systems Membership

Science, Science

**Email:** Sanjiang.Li@uts.edu.au

**Phone:** +61 2 9514 7872

**Fax:**

**Room:**

**Mailing address: **

**Links:**
https://sites.google.com/site/lisanjiang/

https://sites.google.com/site/lisanjiang/Home/publications

## Biography

**Education**

1996-2001 Sichuan University, Chengdu, China

Ph.D. in Mathematics

1992-1996 Shaanxi Normal University, Xi’an, China

B.Sc. in Mathematics

**Employment**

From January 2009: Faculty of Engineering and Information Technology, University of Technology, Sydney

September 2001 – December 2008: Dept. Comp. Sci. & Technol., Tsinghua University

## Teaching areas

Logic in Computer Science

## Research

**Research interests**

My research interests are mainly in spatial reasoning and artificial intelligence. The main objective of my research is to establish expressive representation formalism of spatial knowledge and provide effective reasoning mechanisms. This will contribute significantly to the advancement of knowledge in breakthrough science in qualitative spatial reasoning and smart information use in geographical information systems.

**Research supervision: ** Yes

Dr Weiming Liu, PhD student in Computer Science (graduated in July 2012, received the Chancellor's Award for the best PhD thesis, 2013)

Mr Zhiguo Long, PhD student in Computer Science (from July 2012)

Mr Shufeng Kong, PhD student in Computer Science (from July 2014)

## Projects

### Selected Peer-Assessed Projects

Approximate reasoning with qualitative spatial constraints involving landmarks

Spatial Cognition - Expressive Representation Formalisms and Effective Reasoning Mechanisms

## Publications

### Journal articles

Kong, S., Li, S., Li, Y. & Long, Z. 2017, 'On tree-preserving constraints', *Annals of Mathematics and Artificial Intelligence*, vol. 81, no. 3-4, pp. 241-271.

View description>>

© 2017, Springer International Publishing Switzerland. The study of tractable subclasses of constraint satisfaction problems is a central topic in constraint solving. Tree convex constraints are extensions of the well-known row convex constraints. Just like the latter, every path-consistent tree convex constraint network is globally consistent. However, it is NP-complete to decide whether a tree convex constraint network has solutions. This paper studies and compares three subclasses of tree convex constraints, which are called chain-, path-, and tree-preserving constraints respectively. The class of tree-preserving constraints strictly contains the subclasses of path-preserving and arc-consistent chain-preserving constraints. We prove that, when enforcing strong path-consistency on a tree-preserving constraint network, in each step, the network remains tree-preserving. This ensures the global consistency of consistent tree-preserving networks after enforcing strong path-consistency, and also guarantees the applicability of the partial path-consistency algorithms to tree-preserving constraint networks, which is usually much more efficient than the path-consistency algorithms for large sparse constraint networks. As an application, we show that the class of tree-preserving constraints is useful in solving the scene labelling problem.

Long, Z., Duckham, M., Li, S. & Schockaert, S. 2016, 'Indexing large geographic datasets with compact qualitative representation', *International Journal of Geographical Information Science*, vol. 30, no. 6, pp. 1072-1094.

View description>>

© 2015 Taylor & Francis This paper develops a new mechanism to efficiently compute and compactly store qualitative spatial relations between spatial objects, focusing on topological and directional relations for large datasets of region objects. The central idea is to use minimum bounding rectangles (MBRs) to approximately represent region objects with arbitrary shape and complexity and only store spatial relations that cannot be unambiguously inferred from the relations of corresponding MBRs. We demonstrate, both in theory and practice, that our approach requires considerably less construction time and storage space, and can answer queries more efficiently than the state-of-the-art methods.

### Conferences

Lee, J.H., Li, S., Long, Z. & Sioutis, M. 2016, 'On Redundancy in Simple Temporal Networks', *Frontiers in Artificial Intelligence and Applications*, ECAI 2016, Netherlands, pp. 828-836.

View description>>

The Simple Temporal Problem (STP) has been widely used in various applications to schedule tasks. For dynamical systems, scheduling needs to be efficient and flexible to handle uncertainty and perturbation. To this end, modern approaches usually encode the temporal information as an STP instance. This representation contains redundant information, which can not only take a significant amount of storage space, but also make scheduling inefficient due to the non-concise representation. In this paper, we investigate the problem of simplifying an STP instance by removing redundant information. We show that such a simplification can result in a unique minimal representation without loss of temporal information, and present an efficient algorithm to achieve this task. Evaluation on a large benchmark dataset of STP exhibits a significant reduction in redundant information for the involved instances.

Long, Z., Schockaert, S. & Li, S. 2016, 'Encoding large RCC8 scenarios using rectangular pseudo-solutions', *Principles of Knowledge Representation and Reasoning: Proceedings of the 15th International Conference, KR 2016*, International Conference on Principles of Knowledge Representation and Reasoning, Association for the Advancement of Artificial Intelligence, Cape Town, South Africa, pp. 463-472.

View description>>

Copyright © 2016, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.Most approaches in the field of qualitative spatial reasoning (QSR) use constraint networks to encode spatial scenarios. The size of these networks is quadratic in the number of variables, which has severely limited the real-world application of QSR. In this paper, we propose another representation of spatial scenarios, in which each variable is associated with one or more rectangles. Instead of requiring these rectangles to define a solution of the corresponding constraint network, we construct sequences of rectangles that define partial solutions to progressively weaker constraint networks. We present experimental results that illustrate the effectiveness of this strategy.

Long, Z., Sioutis, M. & Li, S. 2016, 'Efficient path consistency algorithm for large qualitative constraint networks', *Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence*, International Joint Conference on Artificial Intelligence, AAAI Press, New York City, USA, pp. 1202-1208.

View description>>

We propose a new algorithm called DPC+ to enforce partial path consistency (PPC) on qualitative constraint networks. PPC restricts path consistency (PC) to a triangulation of the underlying constraint graph of a network. As PPC retains the sparseness of a constraint graph, it can make reasoning tasks such as consistency checking and minimal labelling of large qualitative constraint networks much easier to tackle than PC. For qualitative constraint networks defined over any distributive subalgebra of well-known spatio-temporal calculi, such as the Region Connection Calculus and the Interval Algebra, we show that DPC+ can achieve PPC very fast. Indeed, the algorithm enforces PPC on a qualitative constraint network by processing each triangle in a triangulation of its underlying constraint graph at most three times. Our experiments demonstrate significant improvements of DPC+ over the state-of-the-art PPC enforcing algorithm.

Sioutis, M., Long, Z. & Li, S. 2016, 'Efficiently reasoning about qualitative constraints through variable elimination', *ACM International Conference Proceeding Series*, Hellenic Conference on Artificial Intelligence (SETN), Association for Computing Machinery Digital Library, Thessaloniki, Greece.

View description>>

© 2016 ACM.We introduce, study, and evaluate a novel algorithm in the context of qualitative constraint-based spatial and temporal reasoning, that is based on the idea of variable elimination, a simple and general exact inference approach in probabilistic graphical models. Given a qualitative constraint network M, our algorithm enforces a particular directional local consistency on M, which we denote by ←-consistency. Our discussion is restricted to distributive subclasses of relations, i.e., sets of relations closed under converse, intersection, and weak composition and for which weak composition distributes over non-empty intersections for all of their relations. We demonstrate that enforcing ←-consistency on a given qualitative constraint network defined over a distributive subclass of relations allows us to decide its satisfiability. The experimentation that we have conducted with random and real-world qualitative constraint networks defined over a distributive subclass of relations of the Region Connection Calculus, shows that our approach exhibits unparalleled performance against competing state-of-the-art approaches for checking the satisfiability of such constraint networks.

### Journal articles

Li, S. & Liu, W. 2015, 'Cardinal directions: a comparison of direction relation matrix and objects interaction matrix', *International Journal of Geographical Information Science*, vol. 29, no. 2, pp. 194-216.

View description>>

© 2014 Taylor & Francis. How to express and reason with cardinal directions between extended objects such as lines and regions is an important problem in qualitative spatial reasoning (QSR), a common subfield of geographical information science and Artificial Intelligence (AI). The direction relation matrix (DRM) model, proposed by Goyal and Egenhofer in 1997, is one very expressive relation model for this purpose. Unlike many other relation models in QSR, the set-theoretic converse of a DRM relation is not necessarily representable in DRM. Schneider et al. regard this as a serious shortcoming and propose, in their work published in ACM TODS (2012), the objects interaction matrix (OIM) model for modelling cardinal directions between complex regions. OIM is also a tiling-based model that consists of two phases: the tiling phase and the interpretation phase. Although it was claimed that OIM is a novel concept, we show that it is not so different from DRM if we represent the cardinal direction of two regions a and b by both the DRM of a to b and that of b to a. Under this natural assumption, we give methods for computing DRMs from OIMs and vice versa, and show that OIM is almost the same as DRM in the tiling phase, and becomes less precise after interpretation. Furthermore, exploiting the similarity between the two models, we prove that the consistency of a complete basic OIM network can be decided in cubic time. This answers an open problem raised by Schneider et al. regarding efficient algorithms for reasoning with OIM.

Li, S. & Liu, W. 2015, 'Cardinal directions: a comparison of direction relation matrix and objects interaction matrix', *International Journal of Geographical Information Science*, vol. 29, no. 2, pp. 194-216.

View description>>

© 2014 Taylor & Francis. How to express and reason with cardinal directions between extended objects such as lines and regions is an important problem in qualitative spatial reasoning (QSR), a common subfield of geographical information science and Artificial Intelligence (AI). The direction relation matrix (DRM) model, proposed by Goyal and Egenhofer in 1997, is one very expressive relation model for this purpose. Unlike many other relation models in QSR, the set-theoretic converse of a DRM relation is not necessarily representable in DRM. Schneider et al. regard this as a serious shortcoming and propose, in their work published in ACM TODS (2012), the objects interaction matrix (OIM) model for modelling cardinal directions between complex regions. OIM is also a tiling-based model that consists of two phases: the tiling phase and the interpretation phase. Although it was claimed that OIM is a novel concept, we show that it is not so different from DRM if we represent the cardinal direction of two regions a and b by both the DRM of a to b and that of b to a. Under this natural assumption, we give methods for computing DRMs from OIMs and vice versa, and show that OIM is almost the same as DRM in the tiling phase, and becomes less precise after interpretation. Furthermore, exploiting the similarity between the two models, we prove that the consistency of a complete basic OIM network can be decided in cubic time. This answers an open problem raised by Schneider et al. regarding efficient algorithms for reasoning with OIM.

Li, S., Long, Z., Liu, W., Duckham, M. & Both, A. 2015, 'On redundant topological constraints', *Artificial Intelligence*, vol. 225, pp. 51-76.

View description>>

Abstract Redundancy checking is an important task in the research of knowledge representation and reasoning. In this paper, we consider redundant qualitative constraints. For a set Γ of qualitative constraints, we say a constraint ( x R y ) in Γ is redundant if it is entailed by the rest of Γ. A prime subnetwork of Γ is a subset of Γ which contains no redundant constraints and has the same solution set as Γ. It is natural to ask how to compute such a prime subnetwork, and when it is unique. We show that this problem is in general intractable, but becomes tractable if Γ is over a tractable subalgebra S of a qualitative calculus. Furthermore, if S is a subalgebra of the Region Connection Calculus RCC8 in which weak composition distributes over nonempty intersections, then Γ has a unique prime subnetwork, which can be obtained in cubic time by removing all redundant constraints simultaneously from Γ. As a by-product, we show that any path-consistent network over such a distributive subalgebra is minimal and globally consistent in a qualitative sense. A thorough empirical analysis of the prime subnetwork upon real geographical data sets demonstrates the approach is able to identify significantly more redundant constraints than previously proposed algorithms, especially in constraint networks with larger proportions of partial overlap relations.

Li, S., Long, Z., Liu, W., Duckham, M. & Both, A. 2015, 'On redundant topological constraints', *Artificial Intelligence*, vol. 225, pp. 51-76.

View description>>

Abstract Redundancy checking is an important task in the research of knowledge representation and reasoning. In this paper, we consider redundant qualitative constraints. For a set Γ of qualitative constraints, we say a constraint ( x R y ) in Γ is redundant if it is entailed by the rest of Γ. A prime subnetwork of Γ is a subset of Γ which contains no redundant constraints and has the same solution set as Γ. It is natural to ask how to compute such a prime subnetwork, and when it is unique. We show that this problem is in general intractable, but becomes tractable if Γ is over a tractable subalgebra S of a qualitative calculus. Furthermore, if S is a subalgebra of the Region Connection Calculus RCC8 in which weak composition distributes over nonempty intersections, then Γ has a unique prime subnetwork, which can be obtained in cubic time by removing all redundant constraints simultaneously from Γ. As a by-product, we show that any path-consistent network over such a distributive subalgebra is minimal and globally consistent in a qualitative sense. A thorough empirical analysis of the prime subnetwork upon real geographical data sets demonstrates the approach is able to identify significantly more redundant constraints than previously proposed algorithms, especially in constraint networks with larger proportions of partial overlap relations.

Schockaert, S. & Li, S. 2015, 'Realizing RCC8 networks using convex regions', *Artificial Intelligence*, vol. 218, pp. 74-105.

View description>>

RCC8 is a popular fragment of the region connection calculus, in which qualitative spatial relations between regions, such as adjacency, overlap and parthood, can be expressed. While RCC8 is essentially dimensionless, most current applications are confined to reasoning about two-dimensional or three-dimensional physical space. In this paper, however, we are mainly interested in conceptual spaces, which typically are high-dimensional Euclidean spaces in which the meaning of natural language concepts can be represented using convex regions. The aim of this paper is to analyze how the restriction to convex regions constrains the realizability of networks of RCC8 relations. First, we identify all ways in which the set of RCC8 base relations can be restricted to guarantee that consistent networks can be convexly realized in respectively 1D, 2D, 3D, and 4D. Most surprisingly, we find that if the relation ‘partially overlaps’ is disallowed, all consistent atomic RCC8 networks can be convexly realized in 4D. If instead refinements of the relation ‘part of’ are disallowed, all consistent atomic RCC8 relations can be convexly realized in 3D. We furthermore show, among others, that any consistent RCC8 network with 2n+1 variables can be realized using convex regions in the n-dimensional Euclidean space.

Zhou, B., Xu, G. & Li, S. 2015, 'The Quintuple Implication Principle of fuzzy reasoning', *Information Sciences*, vol. 297, pp. 202-215.

### Conferences

Kong, S., Li, S., Li, Y. & Long, Z. 2015, 'On tree-preserving constraints', *21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings*, 21st International Conference on Principles and Practice of Constraint Programming (CP 2015), Springer International Publishing, Cork, Ireland.

View description>>

Tree convex constraints are extensions of the well-known row convex constraints. Just like the latter, every path-consistent tree convex constraint network is globally consistent. This paper studies and compares three subclasses of tree convex constraints which are called chain-, path- and tree-preserving constraints respectively. While the tractability of the subclass of chain-preserving constraints has been established before, this paper shows that every chain- or path-preserving constraint network is in essence the disjoint union of several independent connected row convex constraint networks, and hence (re-)establish the tractability of these two subclasses of tree convex constraints. We further prove that, when enforcing arc- and path-consistency on a tree-preserving constraint network, in each step, the network remains tree-preserving. This ensures the global consistency of the tree-preserving network if no inconsistency is detected. Moreover, it also guarantees the applicability of the partial path-consistency algorithm to tree-preserving constraint networks, which is usually more efficient than the path-consistency algorithm for large sparse networks. As an application, we show that the class of tree-preserving constraints is useful in solving the scene labelling problem.

Meng, H., Kou, H. & Li, S. 2015, 'Belief Revision with General Epistemic States', *Online proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence*, Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI Press, Austin, Texas, pp. 1553-1559.

View description>>

In order to properly regulate iterated belief revision, Darwiche and Pearl (1997) model belief revision as revising epistemic states by propositions. An epistemic state in their sense consists of a belief set and a set of conditional beliefs. Although the denotation of an epistemic state can be indirectly captured by a total preorder on the set of worlds, it is unclear how to directly capture the structure in terms of the beliefs and conditional beliefs it contains. In this paper, we first provide an axiomatic characterisation for epistemic states by using nine rules about beliefs and conditional beliefs, and then argue that the last two rules are too strong and should be eliminated for characterising the belief state of an agent. We call a structure which satisfies the first seven rules a general epistemic state (GEP). To provide a semantical characterisation of GEPs, we introduce a mathematical structure called belief algebra, which is in essence a certain binary relation defined on the power set of worlds.We then establish a 1-1 correspondence between GEPs and belief algebras, and show that total preorders on worlds are special cases of belief algebras. Furthermore, using the notion of belief algebras, we extend the classical iterated belief revision rules of Darwiche and Pearl to our setting of general epistemic states.

Sioutis, M., Li, S. & Condotta, J.F. 2015, 'Efficiently characterizing non-redundant constraints in large real world qualitative spatial networks', *IJCAI International Joint Conference on Artificial Intelligence*, International Conference on Artificial Intelligence, AAAI Press, Buenos Aires, Argentina, pp. 3229-3235.

View description>>

RCC8 is a constraint language that serves for qualitative spatial representation and reasoning by encoding the topological relations between spatial entities. We focus on efficiently characterizing non-redundant constraints in large real world RCC8 networks and obtaining their prime networks. For a RCC8 network N a constraint is redundant, if removing that constraint from N does not change the solution set of N. A prime network of N is a network which contains no redundant constraints, but has the same solution set as N. We make use of a particular partial consistency, namely, G⋄-consistency, and obtain new complexity results for various cases of RCC8 networks, while we also show that given a maximal distributive subclass for RCC8 and a network N defined on that subclass, the prunning capacity of G⋄-consistency and ⋄-consistency is identical on the common edges of G and the complete graph of N, when G is a triangulation of the constraint graph of N. Finally, we devise an algorithm based on G⋄-consistency to compute the unique prime network of a RCC8 network, and show that it significantly progresses the state-of-the-art for practical reasoning with real RCC8 networks scaling up to millions of nodes.

Sioutis, M., Li, S. & Condotta, J.F. 2015, 'On redundancy in linked geospatial data', *CEUR Workshop Proceedings*, 2nd Workshop on Linked Data Quality co-located with 12th Extended Semantic Web Conference, Aachen university, Portoroz, Slovenia, pp. 1-8.

View description>>

RCC8 is a constraint language that serves for qualitative spatial representation and reasoning by encoding the topological relations between spatial entities. As such, RCC8 has been recently adopted by GeoSPARQL in an effort to enrich the Semantic Web with qualitative spatial relations. We focus on the redundancy that these data might harbor, which can throttle graph related applications, such as storing, representing, querying, and reasoning. For a RCC8 network N a constraint is redundant, if removing that constraint from N does not change the solution set of N. A prime network of N is a network which contains no redundant constraints, but has the same solution set as N. In this paper, we present a practical approach for obtaining the prime networks of RCC8 networks that originate from the Semantic Web, by exploiting the sparse and loosely connected structure of their constraint graphs, and, consequently, contribute towards offering Linked Geospatial Data of high quality. Experimental evaluation exhibits a vast decrease in the total number of non-redundant constraints that we can obtain from an initial network, while it also suggests that our approach significantly boosts the state-of-the-art approach.

### Other

Long, Z. & Li, S. 2015, 'On distributive subalgebras of qualitative spatial and temporal calculi'.

View description>>

© Springer International Publishing Switzerland 2015. Qualitative calculi play a central role in representing and reasoning about qualitative spatial and temporal knowledge. This paper studies distributive subalgebras of qualitative calculi, which are subalgebras in which (weak) composition distributives over nonempty intersections. The well-known subclass of convex interval relations is an example of distributive subalgebras. It has been proven for RCC5 and RCC8 that path consistent constraint network over a distributive subalgebra is always minimal and strongly n-consistent in a qualitative sense (weakly globally consistent). We show that the result also holds for the four popular qualitative calculi, i.e. Point Algebra, Interval Algebra, Cardinal Relation Algebra, and Rectangle Algebra. Moreover, this paper gives a characterisation of distributive subalgebras, which states that the intersection of a set of m ≥ 3 relations in the subalgebra is nonempty if and only if the intersection of every two of these relations is nonempty. We further compute and generate all maximal distributive subalgebras for those four qualitative calculi mentioned above. Lastly, we establish two nice properties which will play an important role in efficient reasoning with constraint networks involving a large number of variables.

### Journal articles

Cohn, A.G., Li, S., Liu, W. & Renz, J. 2014, 'Reasoning about Topological and Cardinal Direction Relations Between 2-Dimensional Spatial Objects', *The Journal of Artificial Intelligence Research*, vol. 51, pp. 493-532.

Meng, H. & Li, S. 2014, 'A topological characterisation of belief revision over infinite propositional languages', *Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*, vol. 8862, pp. 77-90.

View description>>

© Springer International Publishing Switzerland 2014. Belief revision mainly concerns how an agent updates her belief with new evidence. The AGM framework of belief revision models belief revision as revising theories by propositions. To characterise AGMstyle belief revision operators, Grove proposed in 1988 a representation model using systems of spheres. This ‘spheres’ model is very influential and has been extended to characterise multiple belief revision operators. Several fundamental problems remain unsettled regarding this ‘spheres’ model. In this paper we introduce a topology on the set of all worlds of an infinite propositional language and use this topology to characterise systems of spheres. For each AGM operator ◦, we show that, among all systems of spheres deriving ◦, there is a minimal one which is contained in every other system. We give a topological characterisation of these minimal systems. Furthermore, we propose a method for extending an AGM operator to a multiple revision operator and show by an example that the extension is not unique. This negatively answers an open problem raised by Peppas.

### Conferences

Duckham, M., Li, S., Liu, W. & Long, Z. 2014, 'On Redundant Topological Constraints', *Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014, Vienna, Austria, July 20-24, 2014*.

Meng, H. & Li, S. 2014, 'A Topological Characterisation of Belief Revision over Infinite Propositional Languages', *PRICAI 2014: Trends in Artificial Intelligence - 13th Pacific Rim International Conference on Artificial Intelligence, Gold Coast, QLD, Australia, December 1-5, 2014. Proceedings*, Springer, pp. 77-90.

View description>>

Belief revision mainly concerns how an agent updates her belief with new evidence. The AGM framework of belief revision models belief revision as revising theories by propositions. To characterise AGM-style belief revision operators, Grove proposed in 1988 a representation model using systems of spheres. This ‘spheres’ model is very influential and has been extended to characterise multiple belief revision operators. Several fundamental problems remain unsettled regarding this ‘spheres’ model. In this paper we introduce a topology on the set of all worlds of an infinite propositional language and use this topology to characterise systems of spheres. For each AGM operator ∘, we show that, among all systems of spheres deriving ∘, there is a minimal one which is contained in every other system. We give a topological characterisation of these minimal systems. Furthermore, we propose a method for extending an AGM operator to a multiple revision operator and show by an example that the extension is not unique. This negatively answers an open problem raised by Peppas.

### Journal articles

Duntsch, I. & Li, S. 2013, 'On the homogeneous countable Boolean contact algebra', *Logic and Logical Philosophy*, vol. 22, no. 2, pp. 213-251.

View description>>

Ivo Düntsch, Sanjiang Li. On the homogeneous countable Boolean contact algebra. Logic and Logical Philosophy, 2013, 22, 213251.

Düntsch, I. & Li, S. 2013, 'On the homogeneous countable boolean contact algebra', *Logic and Logical Philosophy*, vol. 22, no. 2, pp. 213-251.

View description>>

In a recent paper, we have shown that the class of Boolean contact algebras (BCAs) has the hereditary property, the joint embedding property and the amalgamation property. By Fraïssé's theorem, this shows that there is a unique countable homogeneous BCA. This paper investigates this algebra and the relation algebra generated by its contact relation. We first show that the algebra can be partitioned into four sets {0}, {1}, K, and L, which are the only orbits of the group of base automorphisms of the algebra, and then show that the contact relation algebra of this algebra is finite, which is the first non-trivial extensional BCA we know which has this property. © Nicolaus Copernicus University (Toruń) 2013.

Li, S., Liu, W. & Wang, S. 2013, 'Qualitative constraint satisfaction problems: An extended framework with landmarks', *Artificial Intelligence Journal*, vol. 201, no. 1, pp. 32-58.

View description>>

Sanjiang Li, Weiming Liu, Shengsheng Wang: Qualitative constraint satisfaction problems: An extended framework with landmarks. Artificial Intelligence, 2013, 201: 32-58

Long, Z. & Li, S. 2013, 'A complete classification of spatial relations using the Voronoi-based nine- intersection model', *International Journal Of Geographical Information Science*, vol. 27, no. 10, pp. 2006-2025.

View description>>

In this article we show that the Voronoi-based nine-intersection (V9I) model proposed by Chen et al. (2001, A Voronoi-based 9-intersection model for spatial relations. International Journal of Geographical Information Science, 15 (3), 201-220) is more ex

### Conferences

Li, J.J. & Li, S. 2013, 'On Finding Approximate Solutions of Qualitative Constraint Networks', *IEEE 25th International Conference on Tools with Artificial Intelligence*, International Conference on Tools with Artificial Intelligence, IEEE, Herndon, VA, USA, pp. 30-37.

View description>>

Qualitative Spatial and Temporal Reasoning (QSTR) represents spatial and temporal information in terms of human comprehensible qualitative predicates and reasons about qualitative information by solving qualitative constraint networks (QCNs). Despite significant progress in the past three decades, more and more evidence has shown that it is inherently hard to find exact solutions for expressive qualitative constraints. In many applications, however, we are often required to make decisions in a very limited time. In these cases, finding a good approximate solution in seconds is much more desirable than waiting days for an exact solution. In this paper, we will exploit the algebraic structure of qualitative calculi (e.g. Interval Algebra and RCC8) as well as their conceptual neighbourhood graphs to develop approximate methods for consistency checking in QSTR. Moreover, we propose and empirically compare four independent methods to serve as tools for finding good approximate solutions for the given qualitative calculi.

Schockaert, S. & Li, S. 2013, 'Combining RCC5 relations with betweenness information', *Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI)*, International Joint Conference on Artificial Intelligence, AAAI Press / International Joint Conferences on Artificial Intelligence, Beijing, China, pp. 1083-1089.

View description>>

RCC5 is an important and well-known calculus for representing and reasoning about mereological relations. Among many other applications, it is pivotal in the formalization of commonsense reasoning about natural categories. In particular, it allows for a qualitative representation of conceptual spaces in the sense of Gärdenfors. To further the role of RCC5 as a vehicle for conceptual reasoning, in this paper we combine RCC5 relations with information about betweenness of regions. The resulting calculus allows us to express, for instance, that some part (but not all) of region B is between regions A and C. We show how consistency can be decided in polynomial time for atomic networks, even when regions are required to be convex. From an application perspective, the ability to express betweenness information allows us to use RCC5 as a basis for interpolative reasoning, while the restriction to convex regions ensures that all consistent networks can be faithfully represented as a conceptual space.

### Journal articles

Li, S. & Cohn, A. 2012, 'Reasoning with Topological and Directional Spatial Information', *Computational Intelligence*, vol. 28, no. 4, pp. 579-616.

View description>>

Sanjiang Li, Anthony G Cohn, Reasoning with Topological and Directional Spatial Information. Computational Intelligence, 2012, 28(4):579-616 (DOI=10.1111/j.1467-8640.2012.00431.x) (PDF) (An early version is available via arXiv) (This is a significant extension of the IJCAI-07 paper)

### Conferences

Duntsch, I. & Li, S. 2012, 'Extension Properties of Boolean Contact Algebras', *Proceedings of the 13th International Conference on Relational and Algebraic Methods in Computer Science (RAMiCS)*, International Conference on Relational and Algebraic Methods in Computer Science, Springer-Verlag, Cambridge, UK, pp. 342-356.

View description>>

Ivo DÃ¼ntsch, Sanjiang Li. Extension Properties of Boolean Contact Algebras, Proceedings of the 13th International Conference on Relational and Algebraic Methods in Computer Science (RAMiCS), pages 342-356, Cambridge, UK, September 17-20, 2012.

Liu, W. & Li, S. 2012, 'Here, There, but Not Everywhere: An Extended Framework for Qualitative Constraint Satisfaction', *Proceedings of the 20th European conference on artificial intelligence (ECAI-2012)*, European conference on artificial intelligence, IOS Press, Montpellier, France, pp. 552-557.

View description>>

Dealing with spatial and temporal knowledge is an indispensable part of almost all aspects of human activities. The qualitative approach to spatial and temporal reasoning (QSTR) provides a promising framework for spatial and temporal knowledge representation and reasoning. QSTR typically represents spatial/temporal knowledge in terms of qualitative relations (e.g., to the east of, after), and reasons with the knowledge by solving qualitative constraints. When formulating a qualitative constraint satisfaction problem (CSP), it is usually assumed that each variable could be âhere, there and everywhere2.â Practical applications e.g. urban planning, however, often require a variable taking values from a certain finite subset of the universe, i.e. require it to be âhere or thereâ. This paper extends the classic framework of qualitative constraint satisfaction by allowing variables taking values from finite domains. The computational complexity of this extended consistency problem is examined for five most important qualitative calculi, viz. Point Algebra, Interval Algebra, Cardinal Relation Algebra, RCC-5, and RCC-8. We show that the extended consistency problem remains in NP, but when only basic constraints are considered, the extended consistency problem for each calculus except Point Algebra is already NP-hard.

Liu, W. & Li, S. 2012, 'Solving Minimal Constraint Networks in Qualitative Spatial and Temporal Reasoning', *Proceedings of the 18th International Conference on Principles and Practice of Constraint Programming (CP-2012)*, International Conference on Principles and Practice of Constraint Programming, Springer-Verlag, Quebec City, Canada, pp. 464-479.

View description>>

Weiming Liu, Sanjiang Li. Solving Minimal Constraint Networks in Qualitative Spatial and Temporal Reasoning, Proceedings of the 18th International Conference on Principles and Practice of Constraint Programming (CP-2012), pages 464-479, Quebec City, Canada, October 8-12, 2012.

Schockaert, S. & Li, S. 2012, 'Convex solutions of RCC8 networks', *Proceedings of the 20th European conference on artificial intelligence (ECAI-2012)*, European conference on artificial intelligence, IOS Press, Montpellier, France, pp. 726-731.

View description>>

RCC8 is one of the most widely used calculi for qualitative spatial reasoning. Although many applications have been explored where RCC8 relations refer to geographical or physical regions in two- or three-dimensional spaces, their use for conceptual reasoning is still at a rather preliminary stage. One of the core obstacles with using RCC8 to reason about conceptual spaces is that regions are required to be convex in this context. We investigate in this paper how the latter requirement impacts the realizability of RCC8 networks. Specifically, we show that consistent RCC8 networks over 2n + 1 variables are guaranteed to have a convex solution in Euclidean spaces of n dimensions and higher. We furthermore prove that our bound is optimal for 2- and 3-dimensional spaces, and that for any number of dimensions n â¥ 4, there exists a network of RCC8 relations over 3n variables which is consistent, but does not allow a convex solution in the n-dimensional Euclidean space.

### Journal articles

Liu, W. & Li, S. 2011, 'On standard models of fuzzy Region Connection Calculus', *International Journal of Approximate Reasoning*, vol. 52, no. 9, pp. 1337-1354.

View description>>

The Region Connection Calculus (RCC) is perhaps the most influential topological relation calculus. Based on the first-order logic, the RCC, however, does not fully meet the needs of applications where the vagueness of entities or relations is important and not ignorable. This paper introduces standard models for the fuzzy region connection calculus (RCC) proposed by Schockaert et al. (2008) [18]. Each of such a standard fuzzy RCC model is induced by a standard RCC model in a natural way. We prove that each standard fuzzy RCC model is canonical in the sense that any satisfiable set of fuzzy RCC8 constraints have a solution in it. Apolynomial realization algorithm is also provided. As a side product,we showsimilar sets of fuzzy constraints have similar solutions if both are satisfiable. This allows us to approximate fuzzy RCC constraints that have arbitrary bounds by those have bounds with finite precision. Â© 2011 Published by Elsevier Inc.

Liu, W. & Li, S. 2011, 'Reasoning about Cardinal Directions between Extended Objects: The NP-Hardness Result', *Artificial Intelligence Journal*, vol. 175, no. 18, pp. 2155-2169.

View description>>

Weiming Liu, Sanjiang Li.Reasoning about Cardinal Directions between Extended Objects: The NP-Hardness Result. Artificial Intelligence, 2011, 175(18): 2155-2169.

### Conferences

Liu, W., Wang, S., Li, S. & Liu, D. 2011, 'Solving Qualitative Constraints Involving Landmarks', *The 17th International Conference on Principles and Practice of Constraint Programming*, International Conference on Principles and Practice, Springer-Verlag Berlin / Heidelberg, Perugia, Italy, pp. 523-537.

View description>>

Consistency checking plays a central role in qualitative spatial and temporal reasoning. Given a set of variables V , and a set of constraints Î taken from a qualitative calculus (e.g. the Interval Algebra (IA) or RCC-8), the aim is to decide if Î is consistent. The consistency problem has been investigated extensively in the literature. Practical applications e.g. urban planning often impose, in addition to those between undetermined entities (variables), constraints between determined entities (constants or landmarks) and variables. This paper introduces this as a new class of qualitative constraint satisfaction problems, and investigates the new consistency problem in several well-known qualitative calculi, e.g. IA, RCC-5, and RCC-8.We show that the usual local consistency checking algorithm works for IA but fails in RCC-5 and RCC-8. We further show that, if the landmarks are represented by polygons, then the new consistency problem of RCC-5 is tractable but that of RCC-8 is NP-complete.

### Journal articles

Liu, W., Zhang, X., Li, S. & Ying, M. 2010, 'Reasoning about Cardinal Directions between Extended Objects', *Artificial Intelligence Journal*, vol. 174, no. 12-13, pp. 951-983.

View description>>

Direction relations between extended spatial objects are important commonsense knowledge. Recently, Goyal and Egenhofer proposed a relation model, known as the cardinal direction calculus (CDC), for representing direction relations between connected plane regions. The CDC is perhaps the most expressive qualitative calculus for directional information, and has attracted increasing interest from areas such as artificial intelligence, geographical information science, and image retrieval. Given a network of CDC constraints, the consistency problem is deciding if the network is realizable by connected regions in the real plane. This paper provides a cubic algorithm for checking the consistency of complete networks of basic CDC constraints, and proves that reasoning with the CDC is in general an NP-complete problem. For a consistent complete network of basic CDC constraints, our algorithm returns a âcanonicalâ solution in cubic time. This cubic algorithm is also adapted to check the consistency of complete networks of basic cardinal constraints between possibly disconnected regions.

### Conferences

Duckham, M., Jeong, M., Li, S. & Renz, J. 2010, 'Decentralized querying of topological relations between regions without using localization', *GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems*, ACM International Symposium on Advances in Geographic Information Systems, ACM, San Jose, USA, pp. 414-417.

View description>>

This paper proposes an efficient, decentralized algorithm for determining the topological relationship between two regions monitored by a geosensor network. Many centralized algorithms already exist for this purpose (used for example in spatial databases

Li, S. 2010, 'A Layered Graph Representation for Complex Regions', *Proceedings of the 12th International Conference on the Principles of Knowledge Representation and Reasoning*, International Conference on the Principles of Knowledge Representation and Reasoning, AAAI, Toronto, Canada, pp. 581-583.

View description>>

Sanjiang Li. A Layered Graph Representation for Complex Regions, in Proceedings of the 12th International Conference on the Principles of Knowledge Representation and Reasoning (KR-10), pages 581-583, Toronto, Canada, May 9-13, 2010

Li, S. & Liu, W. 2010, 'Topological Relations between Convex Regions', *Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI-10)*, National Conference of the American Association for Artificial Intelligence, AAAI Press, Atlanta, Georgia, USA, pp. 321-326.

View description>>

Topological relations between spatial objects are the most important kind of qualitative spatial information. Dozens of relation models have been proposed in the past two decades. These models usually make a small number of distinctions and therefore can only cope with spatial information at a fixed granularity of spatial knowledge. In this paper, we propose a topological relation model in which the topological relation between two convex plane regions can be uniquely represented as a circular string over the alphabet u, v, x, y. A linear algorithm is given to compute the topological relation between two convex polygons. The infinite relation calculus could be used in hierarchical spatial reasoning as well as in qualitative shape description

Liu, W., Li, S. & Renz, J. 2009, 'Combining RCC-8 with Qualitative Direction Calculi: Algorithms and Complexity', *Proceedings of the Twenty-first International Joint Conference on Artificial Intelligence - vol 2*, International Joint Conference on Artificial Intelligence, AAAI Press, Pasadena, California, USA, pp. 854-859.

View description>>

Increasing the expressiveness of qualitative spatial calculi is an essential step towards meeting the requirements of applications. This can be achieved by combining existing calculi in a way that we can express spatial information using relations from both calculi. The great challenge is to develop reasoning algorithms that are correct and complete when reasoning over the combined information. Previous work has mainly studied cases where the interaction between the combined calculi was small, or where one of the two calculiwas very simple. In this paper we tackle the important combination of topological and directional information for extended spatial objects. We combine some of the best known calculi in qualitative spatial reasoning (QSR), the RCC8 algebra for representing topological information, and the Rectangle Algebra (RA) and the Cardinal Direction Calculus (CDC) for directional information. Although CDC is more expressive than RA, reasoning with CDC is of the same order as reasoning with RA. We show that reasoning with basic RCC8 and basic RA relations is in P, but reasoning with basic RCC8 and basic CDC relations is NP-Complete.

### Journal articles

Gao, X., Lu, R., Ouyang, D., Sun, J., Li, S., Shi, C., Yao, T., Lu, R., Han, Z., Wang, J. & Cao, C. 2008, 'AI In China: A Survey', *IEEE Intelligent Systems*, vol. 23, no. 6, pp. 26-32.

View description>>

This article consists of nine short essays discussing research pursued by AI researchers in China and their perspectives on research in several AI subareas. The article first introduces the mechanization of mathematics, an area in which Chinese scientists have made significant contributions. It then discusses research in automated reasoning, temporal and spatial knowledge representation and reasoning, natural language understanding, intelligent diagnosis, multiagent systems, computational intelligence, large-scale knowledge processing, and several research streams integrating AI techniques with methods from other fields. Finally, the article makes suggestions concerning future AI research in China.

Li, S. & Ying, M. 2008, 'Soft constraint abstraction based on semiring homomorphism', *Theoretical Computer Science*, vol. 403, no. 2-3, pp. 192-201.

View description>>

The semiring-based constraint satisfaction problems (semiring CSPs), proposed by Bistarelli, Montanari and Rossi [S. Bistarelli, U. Montanari, F. Rossi, Semiring-based constraints solving and optimization, Journal of the ACM 44 (2) (1997) 201236], is a very general framework of soft constraints. In this paper we propose an abstraction scheme for soft constraints that uses semiring homomorphism. To find optimal solutions of the concrete problem, we first work in the abstract problem and find its optimal solutions, and then use them to solve the concrete problem. In particular, we show that a mapping preserves optimal solutions if and only if it is an order-reflecting semiring homomorphism. Moreover, for a semiring homomorphism ? and a problem P over S, if t is optimal in ?(P), then there is an optimal solution View the MathML source of P such that View the MathML source has the same value as t in ?(P).

### Conferences

Li, J., Kowalski, T., Renz, J. & Li, S. 2008, 'Combining binary constraint networks in qualitative reasoning', *Proceeding of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence: Frontiers in Artificial Intelligence and Applications*, European Conference on Artificial Intelligence, IOS Press, Patras, Greece, pp. 515-519.

View description>>

Constraint networks in qualitative spatial and temporal reasoning are always complete graphs. When one adds an extra element to a given network, previously unknown constraints are derived by intersections and compositions of other constraints, and this may introduce inconsistency to the overall network. Likewise, when combining two consistent networks that share a common part, the combined network may become inconsistent. In this paper, we analyse the problem of combining these binary constraint networks and develop certain conditions to ensure combining two networks will never introduce an inconsistency for a given spatial or temporal calculus. This enables us to maintain a consistent world-view while acquiring new information in relation with some part of it. In addition, our results enable us to prove other important properties of qualitative spatial and temporal calculi in areas such as representability and complexity.

Zhang, X., Liu, W., Li, S. & Ying, M. 2008, 'Reasoning with Cardinal Directions: An Efficient Algorithm', *Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence vol 1*, National Conference of the American Association for Artificial Intelligence, AAAI Press, Chicago, Illinois, USA, pp. 387-392.

View description>>

Direction relations between extended spatial objects are important commonsense knowledge. Recently, Goyal and Egenhofer proposed a formal model, called Cardinal Direction Calculus (CDC), for representing direction relations between connected plane regions. CDC is perhaps the most expressive qualitative calculus for directional information, and has attracted increasing interest from areas such as artificial intelligence, geographical information science, and image retrieval. Given a network of CDC constraints, the consistency problem is deciding if the network is realizable by connected regions in the real plane. This paper provides a cubic algorithm for checking consistency of basic CDC constraint networks. As one byproduct, we also show that any consistent network of CDC constraints has a canonical realization in digital plane. The cubic algorithm can also been adapted to cope with disconnected regions, in which case the current best algorithm is of time complexity O(n5).

### Journal articles

Li, S. 2007, 'A representation theorem for minmax regret policies', *Artificial Intelligence*, vol. 171, no. 1, pp. 19-24.

View description>>

Decision making under uncertainty is one of the central tasks of artificial agents. Due to their simplicity and ease of specification, qualitative decision tools are popular in artificial intelligence. Brafman and Tennenholtz [R.I. Brafman, M. Tennenholtz, An axiomatic treatment of three qualitative decision criteria, J. ACM 47 (3) (2000) 452482] model an agent's uncertain knowledge as her local state, which consists of states of the world that she deems possible. A policy determines for each local state a total preorder of the set of actions, which represents the agent's preference over these actions. It is known that a policy is maximin representable if and only if it is closed under unions and satisfies a certain acyclicity condition. In this paper we show that the above conditions, although necessary, are insufficient for minmax regret and competitive ratio policies. A complete characterization of these policies is obtained by introducing the best-equally strictness.

Li, S. & Nebel, B. 2007, 'Qualitative Spatial Representation and Reasoning: A Hierarchical Approach', *The Computer Journal*, vol. 50, no. 4, pp. 391-402.

View description>>

The ability to reason in space is crucial for agents in order to make informed decisions. Current high-level qualitative approaches to spatial reasoning have serious deficiencies in not reflecting the hierarchical nature of spatial data and human spatial cognition. This article proposes a framework for hierarchical representation and reasoning about topological information, where a continuous model of space is approximated by a collection of discrete sub-models, and spatial information is hierarchically represented in discrete sub-models in a rough set manner. The work is based on the Generalized Region Connection Calculus theory, where continuous and discrete models of space are coped in a unified way. Reasoning issues such as determining the mereological (part-whole) relations between two rough regions are also discussed. Moreover, we consider an important problem that is closely related to map generalization in cartography and Geographical Information Science. Given a spatial configuration at a finer level, we show how to construct a configuration at a coarser level while preserving the mereological relations.

Li, S. & Nebel, B. 2007, 'Qualitative spatial representation and reasoning: A hierarchical approach', *COMPUTER JOURNAL*, vol. 50, no. 4, pp. 391-402.

Li, Y.M. & Li, S.J. 2007, 'Representation of RCC11 composition table', *Ruan Jian Xue Bao/Journal of Software*, vol. 18, no. 10, pp. 2458-2468.

View description>>

This paper is mainly concerned with the relation-algebraic aspects of the well-known Region Connection Calculus (RCC). It is shown that the complemented closed disk algebra is a representation for the relation algebra determined by the RCC11 table, which was first described by Düntsch. The domain of this algebra contains two classes of regions, the closed disks and closures of their complements in the real plane, and the contact relation is the standard Whiteheadean contact (i.e. aCb iff aCb iff a∩≠Φ).

### Conferences

Li, S. 2007, 'Combining Topological and Directional Information for Spatial Reasoning', *Proceedings of the 20th International Joint Conference on Artificial Intelligence*, International Joint Conference on Artificial Intelligence, AAAI Press, Hyderabad, India, pp. 435-440.

View description>>

Current research on qualitative spatial representation and reasoning usually focuses on one single aspect of space. However, in real world applications, several aspects are often involved together. This paper extends the well-known RCC8 constraint language to deal with both topological and directional information, and then investigates the interaction between the two kinds of information. Given a topological (RCC8) constraint network and a directional constraint network, we ask when the joint network is satisfiable. We show that when the topological network is over one of the three maximal tractable subclasses of RCC8, the problem can be reduced into satisfiability problems in the RCC8 algebra and the rectangle algebra (RA). Therefore, reasoning techniques developed for RCC8 and RA can be used to solve the satisfiability problem of a joint network.

### Journal articles

Li, S. 2006, 'A complete classification of topological relations using the 9-intersection method', *International Journal of Geographical Information Science*, vol. 20, no. 6, pp. 589-610.

View description>>

Formalization of topological relations between spatial objects is an important aspect of spatial representation and reasoning. The well-known 9-Intersection Method (9IM) was previously used to characterize topological relations between simple regions, i.e. regions with connected boundary and exterior. This simplified abstraction of spatial objects as simple regions cannot model the variety and complexity of spatial objects. For example, countries like Italy may contain islands and holes. It is necessary that existing formalisms, 9IM in particular, cover this variety and complexity. This paper generalizes 9IM to cope with general regions, where a (general) region is a non-empty proper regular closed subset of the Euclidean plane. We give a complete classification of topological relations between plane regions. For each possible relation we either show that it violates some topological constraints and hence is non-realizable or find two plane regions it relates. Altogether 43 (out of 512) relations are identified as realizable. Among these, five can be realized only between exotic (plane) regions, where a region is exotic if there is another region that has the same boundary but is not its complement. For all the remaining 38 relations, we construct configurations by using sums, differences and complements of discs.

Li, S. 2006, 'A complete classification of topological relations using the 9-intersection method', *International Journal of Geographical Information Science*, vol. 20, no. 6, pp. 589-610.

View description>>

Formalization of topological relations between spatial objects is an important aspect of spatial representation and reasoning. The well-known 9-Intersection Method (9IM) was previously used to characterize topological relations between simple regions, i.e. regions with connected boundary and exterior. This simplified abstraction of spatial objects as simple regions cannot model the variety and complexity of spatial objects. For example, countries like Italy may contain islands and holes. It is necessary that existing formalisms, 9IM in particular, cover this variety and complexity. This paper generalizes 9IM to cope with general regions, where a (general) region is a non-empty proper regular closed subset of the Euclidean plane. We give a complete classification of topological relations between plane regions. For each possible relation we either show that it violates some topological constraints and hence is non-realizable or find two plane regions it relates. Altogether 43 (out of 512) relations are identified as realizable. Among these, five can be realized only between exotic (plane) regions, where a region is exotic if there is another region that has the same boundary but is not its complement. For all the remaining 38 relations, we construct configurations by using sums, differences and complements of discs. © 2006 Taylor & Francis Group, LLC.

Li, S. 2006, 'On Topological Consistency And Realization', *Constraints*, vol. 11, no. 1, pp. 31-51.

View description>>

Topological relations are important in various tasks of spatial reasoning, scene description and object recognition. The RCC8 spatial constraint language developed by Randell, Cui and Cohn (1992) is widely recognized as of particular importance in both t

Li, S. & Li, Y. 2006, 'On The Complemented Disk Algebra', *Journal Of Logic And Algebraic Programming*, vol. 66, no. 2, pp. 195-211.

View description>>

The importance of relational methods in temporal and spatial reasoning has been widely recognised in the last two decades. A quite large part of contemporary spatial reasoning is concerned with the research of relation algebras generated by the

Li, S. & Wang, H. 2006, 'RCC8 binary constraint network can be consistently extended', *Artificial Intelligence*, vol. 170, no. 1, pp. 1-18.

View description>>

The RCC8 constraint language developed by Randell et al. has been popularly adopted by the Qualitative Spatial Reasoning and GIS communities. The recent observation that RCC8 composition table describes only weak composition instead of composition raises questions about Renz and Nebel's maximality results about the computational complexity of reasoning with RCC8. This paper shows that any consistent RCC8 binary constraint network (RCC8 network for short) can be consistently extended. Given ?, an RCC8 network, and z, a fresh variable, suppose xTyset membership, variant? and T is contained in the weak composition of R and S. This means that we can add two new constraints xRz and zSy to ? without changing the consistency of the network. The result guarantees the applicability to RCC8 of one key technique, (Theorem 5) of [J. Renz, B. Nebel, On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus. Artificial Intelligence 108 (1999) 69123], which allows the transfer of tractability of a set of RCC8 relations to its closure under composition, intersection, and converse.

Xia, L. & Li, S. 2006, 'On Minimal Models Of The Region Connection Calculus', *Fundamenta Informaticae*, vol. 69, no. 4, pp. 427-446.

View description>>

Region Connection Calculus (RCC) is one primary formalism of qualitative spatial reasoning. Standard RCC models are continuous ones where each region is infinitely divisible. This contrasts sharply with the predominant use of finite, discrete models in a

### Conferences

Li, S. 2006, 'Combining topological and directional information: First results', *Knowledge Science, Engineering And Management : Lecture Notes in Artificial Intelligence Vol 4092*, International Conference on Knowledge Science, Engineering and Management, Springer-Verlag Berlin, Guilin, China, pp. 252-264.

View description>>

Representing and reasoning about spatial information is important in artificial intelligence and geographical information science. Relations between spatial entities are the most important kind of spatial information. Most current formalisms of spatial relations focus on one single aspect of space. This contrasts sharply with real world applications, where several aspects are usually involved together. This paper proposes a qualitative calculus that combines a simple directional relation model with the well-known topological RCC5 model. We show by construction that the consistency of atomic networks can be decided in polynomial time.

### Journal articles

Li, S., Ying, M. & Li, Y. 2005, 'On Countable RCC Models', *Fundamenta Informaticae*, vol. 65, no. 4, pp. 329-351.

View description>>

Region Connection Calculus (RCC) is the most widely studied formalism of Qualitative Spatial Reasoning. It has been known for some time that each connected regular topological space provides an RCC model. These 'standard' models are inevitable uncountabl

Li, S. & Li, Y. 2004, 'A fuzzy sets theoretic approach to approximate spatial reasoning', *IEEE Transactions on Fuzzy Systems*, vol. 12, no. 6, pp. 745-754.

View description>>

Relational composition-based reasoning has become the most prevalent method for qualitative reasoning since Allen's 1983 work on temporal intervals. Underlying this reasoning technique is the concept of a jointly exhaustive and pairwise disjoint set of relations. Systems of relations such as RCC5 and RCC8 were originally developed for ideal regions, not subject to imperfections such as vagueness or fuzziness which are found in many applications in geographic analysis and image understanding. This paper, however, presents a general method for classifying binary topological relations involving fuzzy regions using the RCC5 or the RCC8 theory. Our approach is based on fuzzy set theory and the theory of consonant random set. Some complete classifications of topological relations between fuzzy regions are also given. Furthermore, two composition operators on spatial relations between fuzzy regions are introduced in this paper. These composition operators provide reasonable relational composition-based reasoning engine for spatial reasoning involving fuzzy regions.

Li, S. & Luo, M. 2004, 'A Note On Stratified L-Real Line And Unit L-Interval', *Fuzzy Sets and Systems*, vol. 147, no. 2, pp. 327-332.

View description>>

We show that the stratified L-real line and the stratified unit L-interval have no non-trivial crisp open sets. Simple characterizations for Boolean-valued stratified L-interval and L-line are also given. (C) 2004 Elsevier B.V. All rights reserved.

Li, S. & Ying, M. 2004, 'Generalized Region Connection Calculus', *Artificial Intelligence*, vol. 160, no. 1-2, pp. 1-34.

View description>>

The Region Connection Calculus (RCC) is one of the most widely referenced system of high-level (qualitative) spatial reasoning. RCC assumes a continuous representation of space. This contrasts sharply with the fact that spatial information obtained from physical recording devices is nowadays invariably digital in form and therefore implicitly uses a discrete representation of space. Recently, Galton developed a theory of discrete space that parallels RCC, but question still lies in that can we have a theory of qualitative spatial reasoning admitting models of discrete spaces as well as continuous spaces? In this paper we aim at establishing a formal theory which accommodates both discrete and continuous spatial information, and a generalization of Region Connection Calculus is introduced. GRCC, the new theory, takes two primitives: the mereological notion of part and the topological notion of connection. RCC and Galton's theory for discrete space are both extensions of GRCC. The relation between continuous models and discrete ones is also clarified by introducing some operations on models of GRCC. In particular, we propose a general approach for constructing countable RCC models as direct limits of collections of finite models. Compared with standard RCC models given rise from regular connected spaces, these countable models have the nice property that each region can be constructed in finite steps from basic regions. Two interesting countable RCC models are also given: one is a minimal RCC model, the other is a countable sub-model of the continuous space R2.

Li, S. & Luo, M. 2003, 'A Negative Answer To T. Kubiak'S Question', *Fuzzy Sets and Systems*, vol. 133, no. 3, pp. 407-409.

View description>>

T. Kubiak raised in 1992 a question about Hausdorffness and compactness in L-topology. It is negatively solved in the present paper by constructing certain L-Hausdorffness and L-compactness axioms. (C) 2002 Elsevier Science B.V. All rights reserved.

Li, S. & Luo, M. 2003, 'FNS Is Not Isomorphic To FTS', *Fuzzy Sets and Systems*, vol. 136, no. 1, pp. 127-131.

View description>>

In this paper, we show that there are exactly c different simultaneously bireffective and bicoreflective subconstructs of FNS, in fact there exists a one-to-one correspondence between those subconstructs of FNS and open sets of (0,1). We also prove that

Li, S. & Luo, M. 2003, 'Generalized Lowen Functors', *Fuzzy Sets and Systems*, vol. 133, no. 3, pp. 375-387.

View description>>

According to their value ranges, L-topological spaces form different categories. Clearly, the investigation on their relationships is certainly important and necessary. Lowen was one of the first authors who had studied the relation between the category

Li, S. & Ying, M. 2003, 'Extensionality Of The RCC8 Composition Table', *Fundamenta Informaticae*, vol. 55, no. 3-4, pp. 363-385.

View description>>

This paper is mainly concerned with the RCC8 composition table entailed by the Region Connection Calculus (RCC), a well-known formalism for Qualitative Spatial Reasoning. This table has been independently generated by Egenhofer in the context of Geograph

Li, S. & Ying, M. 2003, 'Region Connection Calculus: Its models and composition table', *Artificial Intelligence*, vol. 145, no. 1-2, pp. 121-146.

View description>>

Originating in Allen's analysis of temporal relations, the notion of composition table has become a key technique in providing an efficient inference mechanism for a wide class of theories in the field artificial intelligence. This paper is mainly about the consistency-based composition table (RCC8 CT) of the Region Connection Calculus (RCC) raised by Randell, Cui and Cohn. First we show each RCC model is a consistent model of the RCC8 CT. Then after an exhaustive analysis we show that no RCC model can be interpreted extensionally anyway and hence give a negative answer to a conjecture raised by Bennett. All these results are given in an `extensional RCC8 composition table, where we attach to each cell entry in the RCC8 CT a superscript to indicate in what circumstances an extensional interpretation is possible.

Li, S. & Zhang, D. 2003, 'A Non-topologically Generated Hutton-lowen Uniformizable Space', *Quaestiones Methematicae*, vol. 26, no. 4, pp. 471-477.

View description>>

In this note, it is shown that there exist non-topologically generated spaces which are both Lowen uniformizable and Hutton uniformizable. On the other hand, the FNS-coreflection of the Hutton unit interval I(I) is neither Lowen uniformizable nor Hutton uniformizable.

Kong, S., Li, S. & Sioutis, M., 'Exploring Directional Path-Consistency for Solving Constraint Networks'.

View description>>

Among the local consistency techniques used for solving constraint networks, path-consistency (PC) has received a great deal of attention. However, enforcing PC is computationally expensive and sometimes even unnecessary. Directional path-consistency (DPC) is a weaker notion of PC that considers a given variable ordering and can thus be enforced more efficiently than PC. This paper shows that DPC (the DPC enforcing algorithm of Dechter and Pearl) decides the constraint satisfaction problem (CSP) of a constraint language if it is complete and has the variable elimination property (VEP). However, we also show that no complete VEP constraint language can have a domain with more than 2 values. We then present a simple variant of the DPC algorithm, called DPC*, and show that the CSP of a constraint language can be decided by DPC* if it is closed under a majority operation. In fact, DPC* is sufficient for guaranteeing backtrack-free search for such constraint networks. Examples of majority-closed constraint classes include the classes of connected row-convex (CRC) constraints and tree-preserving constraints, which have found applications in various domains, such as scene labeling, temporal reasoning, geometric reasoning, and logical filtering. Our experimental evaluations show that DPC* significantly outperforms the state-of-the-art algorithms for solving majority-closed constraints.

Li, Y., Wang, Q. & Li, S., 'On Quotients of Formal Power Series'.

View description>>

Quotient is a basic operation of formal languages, which plays a key role in the construction of minimal deterministic finite automata (DFA) and the universal automata. In this paper, we extend this operation to formal power series and systemically investigate its implications in the study of weighted automata. In particular, we define two quotient operations for formal power series that coincide when calculated by a word. We term the first operation as (left or right) \emph{quotient}, and the second as (left or right) \emph{residual}. To support the definitions of quotients and residuals, the underlying semiring is restricted to complete semirings or complete c-semirings. Algebraical properties that are similar to the classical case are obtained in the formal power series case. Moreover, we show closure properties, under quotients and residuals, of regular series and weighted context-free series are similar as in formal languages. Using these operations, we define for each formal power series $A$ two weighted automata ${\cal M}_A$ and ${\cal U}_A$. Both weighted automata accepts $A$, and ${\cal M}_A$ is the minimal deterministic weighted automaton of $A$. The universality of ${\cal U}_A$ is justified and, in particular, we show that ${\cal M}_A$ is a sub-automaton of ${\cal U}_A$. Last but not least, an effective method to construct the universal automaton is also presented in this paper.

Liu, W. & Li, S., 'On A Semi-Automatic Method for Generating Composition Tables'.

View description>>

Originating from Allen's Interval Algebra, composition-based reasoning has been widely acknowledged as the most popular reasoning technique in qualitative spatial and temporal reasoning. Given a qualitative calculus (i.e. a relation model), the first thing we should do is to establish its composition table (CT). In the past three decades, such work is usually done manually. This is undesirable and error-prone, given that the calculus may contain tens or hundreds of basic relations. Computing the correct CT has been identified by Tony Cohn as a challenge for computer scientists in 1995. This paper addresses this problem and introduces a semi-automatic method to compute the CT by randomly generating triples of elements. For several important qualitative calculi, our method can establish the correct CT in a reasonable short time. This is illustrated by applications to the Interval Algebra, the Region Connection Calculus RCC-8, the INDU calculus, and the Oriented Point Relation Algebras. Our method can also be used to generate CTs for customised qualitative calculi defined on restricted domains.