UTS site search

Professor Sanjiang Li

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

Image of Sanjiang Li
Professor, Faculty of Engineering & Information Technology
Core Member, Centre for Quantum Computation and Intelligent Systems
Core Member, Joint Research Centre in Intelligent Systems Membership
Science, Science
 
Phone
+61 2 9514 7872

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.

Can supervise: 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)

Logic in Computer Science

Conferences

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/Download from: UTS OPUS
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.
Kong, S., Li, S., Li, Y. & Long, Z. 2015, 'On tree-preserving constraints', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 244-261.
View/Download from: Publisher's site
© Springer International Publishing Switzerland 2015. 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 treepreserving constraints is useful in solving the scene labelling problem.
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, pp. 3229-3235.
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.
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.
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.
View/Download from: UTS OPUS
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, pp. 77-90.
View/Download from: UTS OPUS or Publisher's site
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.
Li, J.J. & Li, S. 2013, 'On finding approximate solutions of qualitative constraint networks', Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI, pp. 30-37.
View/Download from: UTS OPUS or Publisher's site
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. © 2013 IEEE.
Schockaert, S. & Li, S. 2013, 'Combining RCC5 relations with betweenness information', IJCAI International Joint Conference on Artificial Intelligence, pp. 1083-1089.
View/Download from: UTS OPUS
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.
Düntsch, I. & Li, S. 2012, 'Extension properties of boolean contact algebras', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 342-356.
View/Download from: UTS OPUS or Publisher's site
We show that the class of Boolean contact algebras has the joint embedding property and the amalgamation property, and that the class of connected Boolean contact algebras has the joint embedding property but not the amalgamation property. © 2012 Springer-Verlag.
Liu, W. & Li, S. 2012, 'Here, there, but not everywhere: An extended framework for qualitative constraint satisfaction', Frontiers in Artificial Intelligence and Applications, pp. 552-557.
View/Download from: UTS OPUS or Publisher's site
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. © 2012 The Author(s).
Liu, W. & Li, S. 2012, 'Solving minimal constraint networks in qualitative spatial and temporal reasoning', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 464-479.
View/Download from: UTS OPUS or Publisher's site
The minimal label problem (MLP) (also known as the deductive closure problem) is a fundamental problem in qualitative spatial and temporal reasoning (QSTR). Given a qualitative constraint network ?, the minimal network of ? relates each pair of variables (x,y) by the minimal label of (x,y), which is the minimal relation between x,y that is entailed by network ?. It is well-known that MLP is equivalent to the corresponding consistency problem with respect to polynomial Turing-reductions. This paper further shows, for several qualitative calculi including Interval Algebra and RCC-8 algebra, that deciding the minimality of qualitative constraint networks and computing a solution of a minimal constraint network are both NP-hard problems. © 2012 Springer-Verlag.
Schockaert, S. & Li, S. 2012, 'Convex solutions of RCC8 networks', Frontiers in Artificial Intelligence and Applications, pp. 726-731.
View/Download from: UTS OPUS or Publisher's site
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. © 2012 The Author(s).
Liu, W., Wang, S., Li, S. & Liu, D. 2011, 'Solving qualitative constraints involving landmarks', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 523-537.
View/Download from: UTS OPUS or Publisher's site
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. © 2011 Springer-Verlag.
Li, S. & Liu, W. 2010, 'Topological relations between convex regions', Proceedings of the National Conference on Artificial Intelligence, pp. 321-326.
View/Download from: UTS OPUS
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. Copyright © 2010, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
Duckham, M., Jeong, M.H., 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, pp. 414-417.
View/Download from: UTS OPUS or Publisher's site
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). However, these algorithms are not suited to decentralized spatial computing environments, like geosensor networks, which must operate without global knowledge of the system state and without centralized control. Unlike many existing decentralized spatial algorithms, the proposed algorithm is also able to operate in the absence of information about a node's coordinate location. This makes the algorithm suitable for applications of geosensor networks where GPS or other positioning systems are unavailable or unreliable. The algorithm approach is founded on the well-known 4-intersection model, using in-network data aggregation and spatial filtering (involving nodes only at some region boundaries). This ensures only a relatively small proportion of the network is involved in computation, thus increasing efficiency. Our analysis shows that while the overall communication complexity of the algorithm is O(n), the load balancing is optimal leading to a constant O(1) communication complexity for individual nodes. This expectation is confirmed with empirical investigation using simulation, which demonstrates the practical efficiency of the algorithm. © 2010 ACM.
Li, S. 2010, 'A layered graph representation for complex regions', Principles of Knowledge Representation and Reasoning: Proceedings of the 12th International Conference, KR 2010, pp. 581-583.
View/Download from: UTS OPUS
This paper proposes a layered graph model for representing the internal structure of complex plane regions, where each node represents the closure of a connected component of the interior or exterior of a complex region. The model provides a complete representation in the sense that the (global) nineintersections between the interiors, the boundaries, and the exteriors of two complex regions can be determined by the (local) RCC8 relations between associated simple regions. Copyright © 2010, Association for the Advancement of Artificial Intelligence.
Liu, W., Li, S. & Renz, J. 2009, 'Combining RCC-8 with qualitative direction calculi: Algorithms and complexity', IJCAI International Joint Conference on Artificial Intelligence, pp. 854-859.
View/Download from: UTS OPUS
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.
Zhang, X., Liu, W., Li, S. & Ying, M. 2008, 'Reasoning with cardinal directions: An efficient algorithm', Proceedings of the National Conference on Artificial Intelligence, pp. 387-392.
View/Download from: UTS OPUS
Direction relations between extended spatial objects are important commonsense knowledge. Recently, Goyal and Egen-hofer 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).Copyright © 2008, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
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/Download from: UTS OPUS
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.
Li, S. 2007, 'Combining topological and directional information for spatial reasoning', IJCAI International Joint Conference on Artificial Intelligence, pp. 435-440.
View/Download from: UTS OPUS
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.
Li, S. 2006, 'Combining topological and directional information: First results', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 252-264.
View/Download from: UTS OPUS
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. © Springer-Verlag Berlin Heidelberg 2006.

Journal articles

Schockaert, S. & Li, S. 2015, 'Realizing RCC8 networks using convex regions', Artificial Intelligence, vol. 218, pp. 74-105.
View/Download from: UTS OPUS or Publisher's site
© 2014 Elsevier B.V. All rights reserved. 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 + 1variables 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.
View/Download from: UTS OPUS or Publisher's site
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/Download from: Publisher's site
© 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.
Long, Z., Duckham, M., Li, S. & Schockaert, S. 2015, 'Indexing large geographic datasets with compact qualitative representation', International Journal of Geographical Information Science.
View/Download from: Publisher's site
© 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.
Cohn, A.G., Li, S., Liu, W. & Renz, J. 2014, 'Reasoning about topological and cardinal direction relations between 2-dimensional spatial objects', Journal of Artificial Intelligence Research, vol. 51, pp. 493-532.
View/Download from: UTS OPUS
© 2014 AI Access Foundation. All rights reserved. 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 multiple 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 calculi was 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, the RCC8 algebra for representing topological information, and the Rectangle Algebra (RA) and the Cardinal Direction Calculus (CDC) for directional information. We consider two different interpretations of the RCC8 algebra, one uses a weak connectedness relation, the other uses a strong connectedness relation. In both interpretations, we show that reasoning with topological and directional information is decidable and remains in NP. Our computational complexity results unveil the significant differences between RA and CDC, and that between weak and strong RCC8 models. Take the combination of basic RCC8 and basic CDC constraints as an example: we show that the consistency problem is in P only when we use the strong RCC8 algebra and explicitly know the corresponding basic RA constraints.
Li, S. & Liu, W. 2014, 'Cardinal directions: a comparison of direction relation matrix and objects interaction matrix', International Journal of Geographical Information Science.
View/Download from: Publisher's site
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.
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/Download from: Publisher's site
© 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.
Li, S., Liu, W. & Wang, S. 2013, 'Qualitative constraint satisfaction problems: An extended framework with landmarks', Artificial Intelligence, vol. 201, pp. 32-58.
View/Download from: UTS OPUS or Publisher's site
Dealing with spatial and temporal knowledge is an indispensable part of almost all aspects of human activity. The qualitative approach to spatial and temporal reasoning, known as Qualitative Spatial and Temporal Reasoning (QSTR), typically represents spatial/temporal knowledge in terms of qualitative relations (e.g., to the east of, after), and reasons with spatial/temporal knowledge by solving qualitative constraints. When formulating qualitative constraint satisfaction problems (CSPs), it is usually assumed that each variable could be "here, there and everywhere".1 Practical applications such as urban planning, however, often require a variable to take its value from a certain finite domain, i.e. it is required to be 'here or there, but not everywhere'. Entities in such a finite domain often act as reference objects and are called "landmarks" in this paper. The paper extends the classical framework of qualitative CSPs by allowing variables to take values from finite domains. The computational complexity of the consistency problem in this extended framework is examined for the five most important qualitative calculi, viz. Point Algebra, Interval Algebra, Cardinal Relation Algebra, RCC5, and RCC8. We show that all these consistency problems remain in NP and provide, under practical assumptions, efficient algorithms for solving basic constraints involving landmarks for all these calculi. © 2013 Elsevier B.V.
Duntsch, I. & Li, S. 2013, 'On the homogeneous countable Boolean contact algebra', Logic and Logical Philosophy, vol. 22, no. 2, pp. 213-251.
View/Download from: UTS OPUS or Publisher's site
Ivo Düntsch, Sanjiang Li. On the homogeneous countable Boolean contact algebra. Logic and Logical Philosophy, 2013, 22, 213251.
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/Download from: UTS OPUS or Publisher's site
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 expressive than what has been believed before. Given any two spatial entities A and B, the V9I relation between A and B is represented as a 3 3 Boolean matrix. For each pair of types of spatial entities that is, points, lines, and regions, we first show that most Boolean matrices do not represent a V9I relation by using topological constraints and the definition of Voronoi regions. Then, we provide illustrations for all the remaining matrices. This guarantees that our method is sound and complete. In particular, we show that there are 18 V9I relations between two areas with connected interior, while there are only nine four-intersection relations. Our investigations also show that, unlike many other spatial relation models, V9I relations are context or shape sensitive. That is, the existence of other entities or the shape of the entities may affect the validity of certain relations. © 2013 Taylor & Francis.
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/Download from: Publisher's site
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 Frassé'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. & Cohn, A.G. 2012, 'Reasoning with topological and directional spatial information', Computational Intelligence, vol. 28, no. 4, pp. 579-616.
View/Download from: UTS OPUS or Publisher's site
Current research on qualitative spatial representation and reasoning mainly focuses on one single aspect of space. In real-world applications, however, multiple spatial aspects are often involved simultaneously. This paper investigates problems arising in reasoning with combined topological and directional information. We use the RCC8 algebra and the rectangle algebra (RA) for expressing topological and directional information, respectively. We give examples to show that the bipath-consistency algorithm Bipath-Consistency is incomplete for solving even basic RCC8 and RA constraints. If topological constraints are taken from some maximal tractable subclasses of RCC8, and directional constraints are taken from a subalgebra, termed DIR49, of RA, then we show that Bipath-Consistency is able to separate topological constraints from directional ones. This means, given a set of hybrid topological and directional constraints from the above subclasses of RCC8 and RA, we can transfer the joint satisfaction problem in polynomial time to two independent satisfaction problems in RCC8 and RA. For general RA constraints, we give a method to compute solutions that satisfy all topological constraints and approximately satisfy each RA constraint to any prescribed precision. © 2012 Wiley Periodicals, Inc.
Liu, W. & Li, S. 2011, 'Reasoning about cardinal directions between extended objects: The NP-hardness result', Artificial Intelligence, vol. 175, no. 18, pp. 2155-2169.
View/Download from: UTS OPUS or Publisher's site
The cardinal direction calculus (CDC) proposed by Goyal and Egenhofer is a very expressive qualitative calculus for directional information of extended objects. Early work has shown that consistency checking of complete networks of basic CDC constraints is tractable, while reasoning with the CDC in general is NP-hard. This paper shows, however, that if some constraints are unspecified, then consistency checking of incomplete networks of basic CDC constraints is already intractable. This draws a sharp boundary between the tractable and intractable subclasses of the CDC. The result is achieved by a reduction from the well-known 3-SAT problem. © 2011 Elsevier B.V. All rights reserved.
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/Download from: UTS OPUS or Publisher's site
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. A polynomial realization algorithm is also provided. As a side product, we show similar 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 Elsevier Ltd. All rights reserved.
Liu, W., Zhang, X., Li, S. & Ying, M. 2010, 'Reasoning about cardinal directions between extended objects', Artificial Intelligence, vol. 174, no. 12-13, pp. 951-983.
View/Download from: UTS OPUS or Publisher's site
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. © 2010 Elsevier B.V. All rights reserved.
Li, S. & Ying, M. 2008, 'Soft constraint abstraction based on semiring homomorphism', Theoretical Computer Science, vol. 403, no. 2-3, pp. 192-201.
View/Download from: UTS OPUS or Publisher's site
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) 201-236], 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 over(t, ?) of P such that over(t, ?) has the same value as t in ? (P). © 2008 Elsevier B.V. All rights reserved.
Gao, X.S., Ouyang, D.T., San, J.G., Li, S.J., Yao, T.S., Lu, R.Z., Shi, C.Y., Han, Z.G., Wang, J., Cao, C.G. & Lu, R. 2008, 'AI in China: A survey', IEEE Intelligent Systems, vol. 23, no. 6, pp. 26-32.
View/Download from: UTS OPUS
Chinese researchers have made contributions to many key AI (artificial intelligence) areas. Chinese researchers have extended mechanized methods for differential-difference (DD) equations, which are of practical importance. Researchers have developed the zero decomposition algorithms for DD equations, which can help solve the perfect ideal-membership problems in DD polynomial systems and prove theorems that can be represented by DD equations. Researchers have used Stewart platform in the development of key components of integrated circuit equipment. Y. Liu and colleagues have proposed a spatial-relation model for internal cardinal directions. S. Li and M. Ying have proposed GRCC (generalized RCC), a formalism for topological information that generalizes the RCC theory and accommodates both continuous and discrete spatial models. Chinese AI researchers have applied multiobjective genetic algorithm (GAs) to improve GPS signal acquisition. Research has also been conducted on an object-orientation based design framework for software agents and the operational semantics of MAS components.
Li, S. 2007, 'A representation theorem for minmax regret policies', Artificial Intelligence, vol. 171, no. 1, pp. 19-24.
View/Download from: UTS OPUS or Publisher's site
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) 452-482] 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. © 2006 Elsevier B.V. All rights reserved.
Li, S. & Nebel, B. 2007, 'Qualitative spatial representation and reasoning: A hierarchical approach', Computer Journal, vol. 50, no. 4, pp. 391-402.
View/Download from: UTS OPUS or Publisher's site
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. © The Author 2007. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved.
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/Download from: Publisher's site
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???).
Li, S. & Wang, H. 2006, 'RCC8 binary constraint network can be consistently extended', Artificial Intelligence, vol. 170, no. 1, pp. 1-18.
View/Download from: UTS OPUS or Publisher's site
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 xTy?? 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) 69-123], which allows the transfer of tractability of a set of RCC8 relations to its closure under composition, intersection, and converse. © 2005 Elsevier B.V. All rights reserved.
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/Download from: UTS OPUS or Publisher's site
Xia, L. & Li, S. 2006, 'On minimal models of the Region Connection Calculus', Fundamenta Informaticae, vol. 69, no. 4, pp. 427-446.
View/Download from: UTS OPUS
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 applications. In a recent paper, Li et al. (2004) initiate a study of countable models that can be constructed step by step from finite models. Of course, some basic problems are left unsolved, for example, how many non-isomorphic countable RCC models are there? This paper investigates these problems and obtains the following results: (i) the exotic RCC model described by Gotts (1996) is isomorphic to the minimal model given by Li and Ying (2004); (ii) there are continuum many non-isomorphic minimal RCC models, where a model is minimal if it can be isomorphically embedded in each RCC model.
Li, S. & Li, Y. 2006, 'On the complemented disk algebra', Journal of Logic and Algebraic Programming, vol. 66, no. 2, pp. 195-211.
View/Download from: UTS OPUS or Publisher's site
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 "part of" and "connection" relations in various domains. This paper is devoted to the study of one particular relation algebra appeared in the literature, viz. the complemented disk algebra. This algebra was first described by Düntsch [I. Düntsch, A tutorial on relation algebras and their application in spatial reasoning, Given at COSIT, August 1999, Available from: ?http://www.cosc.brocku.ca/ ~duentsch/papers/relspat.html?] and then, Li et al. [Y. Li, S. Li, M. Ying, Relational reasoning in the Region Connection Calculus, Preprint, 2003, Available from: http://arxiv.org/abs/cs/0505041] showed that closed disks and their complements provides a representation. This set of regions is rather restrictive and, thus, of limited practical values. This paper will provide a general method for generating representations of this algebra in the framework of Region Connection Calculus. In particular, connected regions bounded by Jordan curves and their complements is also such a representation. © 2005 Elsevier Inc. All rights reserved.
Li, S. 2006, 'On topological consistency and realization', Constraints, vol. 11, no. 1, pp. 31-51.
View/Download from: UTS OPUS or Publisher's site
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 is widely recognized as of particular importance in both the research fields of qualitative spatial reasoning (QSR) and geographical information science. Given a network of RCC8 relations naturally we ask when it is consistent and if this is the case can we have a realization in a certain spatial model? This paper gives a direct and simple algorithm for generating realizations of path-consistent networks of RCC8 base relations. As a result we also show that each consistent network of RCC8 relations has a realization in the digital plane (with either 4- or 8-connections) and in any RCC model. © Springer Science + Business Media LLC 2006.
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/Download from: Publisher's site
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.
Li, S., Ying, M. & Li, Y. 2005, 'On countable RCC models', Fundamenta Informaticae, vol. 65, no. 4, pp. 329-351.
View/Download from: UTS OPUS
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 uncountable and regions there cannot be represented finitely. This paper, however, draws researchers' attention to RCC models that can be constructed from finite models hierarchically. Compared with those 'standard' models, these countable models have the nice property that regions where can be constructed in finite steps from basic ones. We first investigate properties of three countable models introduced by Düuntsch, Stell, Li and Ying, resp. In particular, we show that (i) the contact relation algebra of our minimal model is not atomic complete; and (ii) these three models are non-isomorphic. Second, for each n>0, we construct a countable RCC model that is a sub-model of the standard model over the Euclidean unit n-cube; and show that all these countable models are non-isomorphic. Third, we show that every finite model can be isomorphically embedded in any RCC model. This leads to a simple proof for the result that each consistent spatial network has a realization in any RCC model.
Li, S. & Ying, M. 2004, 'Generalized region connection calculus', Artificial Intelligence, vol. 160, no. 1-2, pp. 1-34.
View/Download from: UTS OPUS or Publisher's site
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 ?2. © 2004 Elsevier B.V. All rights reserved.
Li, Y. & Li, S. 2004, 'A fuzzy sets theoretic approach to approximate spatial reasoning', IEEE Transactions on Fuzzy Systems, vol. 12, no. 6, pp. 745-754.
View/Download from: UTS OPUS or Publisher's site
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. © 2004 IEEE.
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/Download from: UTS OPUS or Publisher's site
The stratified L-real line and the unit L-interval having no non-trivial crisp open sets are studied. A simple characterization of Boolean valued stratified L-interval and L-line is also sanalyzed. The background spaces of I(L) and R(L) are found to be trivial. It is concluded that l a(?) is a product topology on IA.
Li, S. & Ying, M. 2003, 'Region connection calculus: Its models and composition table', Artificial Intelligence, vol. 145, no. 1-2, pp. 121-146.
View/Download from: UTS OPUS or Publisher's site
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. © 2002 Elsevier Science B.V. All rights reserved.
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/Download from: UTS OPUS or Publisher's site
Certain L-Hausdorffness and L-compactness axioms were constructed. It was pointed out that the characteristic functor ? was a right adjoint of the Martin functor. It was concluded that L-compactness didn't imply ultra-compactness.
Li, S. & Ying, M. 2003, 'Extensionality of the RCC8 Composition Table', Fundamenta Informaticae, vol. 55, no. 3-4, pp. 363-385.
View/Download from: UTS OPUS
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 Geographic Information Systems. It has been known for some time that the table is not extensional for each RCC model. This paper however shows that the Egenhofer model is indeed an extensional one for the RCC8 composition table. Moreover this model is the maximal extensional one for the RCC8 composition table in a sense.
Li, S. & Luo, M. 2003, 'FNS is not isomorphic to FTS', Fuzzy Sets and Systems, vol. 136, no. 1, pp. 127-131.
View/Download from: UTS OPUS or Publisher's site
In this paper, we show that there are exactly c different simultaneously bireflective 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 FNS and FNBS are mutually complemented in the complete lattice of simultaneously bireflective and bicoreflective subconstructs of FTS. As a result we get that FNS is not isomorphic to FTS. © 2002 Elsevier Science B.V. All rights rserved.
Li, S. & Luo, M. 2003, 'Generalized Lowen functors', Fuzzy Sets and Systems, vol. 133, no. 3, pp. 375-387.
View/Download from: UTS OPUS or Publisher's site
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 of I-topological spaces and that of topological spaces. He introduced two well-known functors: ? and ?. Later, these functors, namely Lowen functors, were extended by different authors for various kinds of lattices studying the relation between L-TOP and TOP. In this paper, we introduce two functors ? f and ? f between L 1-TOP and L 2-TOP for each Scott continuous mapping f: L 2 ? L 1, where L 1 and L 2 are arbitrary two completely distributive lattices. Some topological properties related to these functors are revealed, e.g., for L i-topological space (X i, ? i) (i = 1,2), both ? f(X 1, ? 1) and ? f(X 2, ? 2) are Lowen spaces; in the case that f is the identity mapping on a linearly ordered complete lattice, for L-topological space (X, ?), ? f(?) is the finest Lowen topology on X contained in ? and ? f(?) is the coarsest Lowen topology on X containing ?, etc. © 2002 Elsevier Science B.V. All rights reserved.
Li, S. & Zhang, D. 2003, 'A non-topologically generated Hutton-Lowen uniformizable space', Quaestiones Mathematicae, vol. 26, no. 4, pp. 471-477.
View/Download from: UTS OPUS
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. © 2003 NISC Pty Ltd.

Other

Li, S., Long, Z., Liu, W., Duckham, M. & Both, A. 2015, 'On redundant topological constraints'.
View/Download from: Publisher's site
© 2015 Elsevier B.V. All rights reserved. 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 (xRy) 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.
Long, Z. & Li, S. 2015, 'On distributive subalgebras of qualitative spatial and temporal calculi'.
View/Download from: Publisher's site
© 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.