What Is a Qualitative Calculus? A General Framework
Lecture notes in computer sciencePublished 1 January 2004Open access
Gérard Ligozat, Jochen Renz
Citations138
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that the natural algebraic object governing this kind of calculus is a non-associative algebra (in the sense of Maddux), and that the notion of weak representation is the right notion for describing most basic properties.
Abstract
International audience
Keywords
Computer Science
Communications of the ACMMaintaining knowledge about temporal intervals
7,550 Citations1983James F. Allen
An interval-based temporal logic is introduced, together with a computationally effective reasoning algorithm based on constraint propagation, which is notable in offering a delicate balance between space and time.
A Spatial Logic based on Regions and Connection.
1,927 Citations1992David Randell, Zhanfeng Cui +1 more
An interval logic for reasoning about space is described, which supports a simpler ontology, has fewer functions and relations, yet does not su(cid:11)er in terms of its useful expressiveness.
Artificial IntelligenceTemporal constraint networks
1,800 Citations1991Rina Dechter, Itay Meiri +1 more
It is shown that the STP, which subsumes the major part of Vilain and Kautz's point algebra, can be solved in polynomial time and the applicability of path consistency algorithms as preprocessing of temporal problems is studied, to demonstrate their termination and bound their complexities.
Constraint propagation algorithms for temporal reasoning
643 Citations1986Marc Vilain, Henry Kautz
Computing the consequences of temporal assertions is shown to be computationally intractable in the interval-based representation, but not in the point-based one, but a fragment of the interval language can be expressed using the point language and benefits from the tractability of the latter.
Journal of Visual Languages & ComputingReasoning about Cardinal Directions
296 Citations1998Gérard Ligozat
This paper is about the complexity of reasoning about cardinal directions in 2D space and considers the problem of picture description as presented by Chang and Jungert [2].
Relational Methods in Computer Science
245 Citations1997Chris Brink, Wolfram Kahl +1 more
Journal of the ACMOn binary constraint problems
190 Citations1994Peter B. Ladkin, Roger D. Maddux
The concepts of binary constraint satisfaction problems can be naturally generalized to the relation algebras of Tarski, and a class of examples over a fixed finite algebra on which all iterative local algorithms, whether parallel or sequential, must take quadratic time is given.
Transactions of the American Mathematical SocietySome varieties containing relation algebras
153 Citations1982Roger D. Maddux
National Conference on Artificial IntelligenceOn generalized interval calculi
99 Citations1991Gérard Ligozat
The calculus of generalized intervals, which subsumes extensions of the calculus of time intervals in an algebraic setting, is investigated and it is shown that, as an order, it is a distributive lattice whose properties express the topological properties of the set of (p,q)-relations.
National Conference on Artificial IntelligenceWeak representations of interval algebras
44 Citations1990Gérard Ligozat
This paper considers the algebra An of n-intervals, which coincides with Allen's algebra for n=2, and proves that An has a unique countable representation up to isomorphism for all n2 1.
A spatial odyssey of the interval algebra: 1. directed intervals
41 Citations2001Jochen Renz
An algebra for qualitative spatial representation and reasoning about directed intervals, identify tractable subsets, and show that path-consistency is sufficient for deciding consistency for a particular subset which contains all base relations are developed.
International Joint Conference on Artificial IntelligenceA New Framework for Reasoning about Points, Intervals and Durations
37 Citations1999Arun K. Pujari, Abdul Sattar
This work identifies a subclass for which enforcing 4-consistency suffices to ensure the global consistency of the tractable subclasses of PIDN, and proves that this subclass is maximal for qualitative constraints.
Applied IntelligenceSpatial Reasoning About Points in a Multidimensional Setting
26 Citations2002Philippe Balbiani, Jean-François Condotta
It is demonstrated that the consistency problem of strongly preconvex n-point networks can be decided in polynomial time by means of the weak path-consistency method for all n ≥ 1 and it is proved that the concept of strong preconveXity corresponds to the one of ORD-Horn representability.
HAL (Le Centre pour la Communication Scientifique Directe)Tractable relations in temporal reasoning: pre-convex relations
23 Citations1994Gérard Ligozat
It is shown that the set of pre-convex relations in the point-and-interval calculus is the maximal tractable subclass containing all atomic relations.
Lecture notes in computer scienceA Tractable Subclass of the Block Algebra: Constraint Propagation and Preconvex Relations
22 Citations1999Philippe Balbiani, Jean-François Condotta +1 more
This paper defines, for every n ≥ 1, n-dimensional block algebra as a set of relations, the block relations, together with the fundamental operations of composition, conversion and intersection, and examines the 13n atomic relations of this algebra which constitute the exhaustive list of the permitted relations between two blocks.
HAL (Le Centre pour la Communication Scientifique Directe)Spatial and temporal reasoning : Beyond Allens' Calculus
16 Citations2003Gérard Ligozat, Debasis Mitra +1 more
On the consistency problem for the INDU calculus
14 Citations2004Philippe Balbiani, Jean-François Condotta +1 more
The intractability of the consistency problem for the subset of preconvex relations is proved and the tractability of strongly preconveX relations is shown.
Qualitative Reasoning with Arbitrary Angular Directions
11 Citations2002Debasis Mitra
This work has introduced a generalized framework for qualitative reasoning with relative directions, with a parameterized angular zoning scheme, and provided a maximal tractable subclass.
Lecture notes in computer scienceTangent Circle Algebras
3 Citations2002Ivo Düntsch, Marc Roubens
This paper investigates relation algebras which arise in the context of preference relations, and studies the tangent circle orders introduced in [1].