Abstract
We define, in this paper, 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. We examine the 13n atomic relations of this algebra which constitute the exhaustive list of the permitted relations that can hold between two blocks whose sides are parallel to the axes of some orthogonal basis in the n-dimensional Euclidean space over the field of real numbers. We organize these atomic relations in ascending order with the intention of defining the concept of convexity as well as the one of preconvexity. We will confine ourselves to the issue of the consistency of block networks which consist of sets of constraints between a finite number of blocks. Showing that the concepts of convexity and preconvexity are preserved by the fundamental operations, we prove the tractability of the problem of the consistency of strongly preconvex block networks, on account of our capacity for deciding it in polynomial time by means of the path-consistency algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, Volume 26, 832–843, 1983.
J. Allen, P. Hayes. A common sense theory of time. A. Joshi (editor), IJCAI-85. Proc. of the 9th International Joint Conf. on Artificial Intelligence, Volume one, 528–531, Morgan Kaufmann, 1985.
P. Balbiani, J-F. Condotta and Luis Fariñas del Cerro. A model for reasoning about bidimensional temporal relations. A.G. Cohn, L. Schubert, and S.C. Shapiro (editors), KR’98. Proc. of the 6th International Conf. on Principles of Knowledge Representation and Reasoning, 124–130, 1998.
M. Egenhofer and R. Franzosa. Point-set topological spatial relations. International Journal of Geographical Information Systems 5(2), 161–174, 1991.
C. Freksa. Using orientation information for qualitative spatial reasoning. A.U. Frank, I. Campari, and U. Formentini (editors), Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, Proc. of the International Conf. GIS — From Space to Territory, 162–178, Springer Verlag, 1992.
H. Güsgen. Spatial reasoning based on Allen’s temporal logic. Report ICSI TR89-049, International Computer Science Institute, 1989.
G. Ligozat. Tractable relations in temporal reasoning: pre-convex relations. ECAI-94. Workshop on Spatial and Temporal Reasoning, 99–108, 1994.
G. Ligozat. A new proof of tractability for ORD-Horn relations. AAAI-96. Proc. of the 13th National Conf. on Artificial Intelligence, Volume one, 395–401, AAAI Press and MIT Press, 1996.
A. K. Mackworth. Consistency in networks of relations Artificial Intelligence, Volume eight, 99–118, 1977.
A. Mukerjee, G. Joe. A Qualitative Model For Space. AAAI-90. Proc. of the 8th National Conf. on Artificial Intelligence, Volume two, 721–727, AAAI Press and MIT Press, 1990.
B. Nebel, H.-J. Bürckert. Reasoning about temporal relations: a maximal tractable subclass of Allen’s interval algebra. AAAI-94. Proc. of the 12th National Conf. on Artificial Intelligence, Volume one, 356–361, AAAI Press and MIT Press, 1994.
D. Randell, Z. Cui, T. Cohn. An interval logic for space based on “connection”. B. Neumann (editor), ECAI-92. Proc. of the 10th European Conf. on Artificial Intelligence, 394–398, Wiley, 1992.
D. Randell, Z. Cui, T. Cohn. A spatial logic based on regions and connection. B. Nebel, C. Rich, and W. Swartout (editors), KR’92. Proc. of the 3rd International Conf. on Principles of Knowledge Representation and Reasoning, 165–176, Morgan Kaufmann, 1992.
J. Renz, B. Nebel. On the complexity of qualitative spatial reasoning: a maximal tractable fragment of the region connection calculus. M. Polack (editor), IJCAI-97. Proc. of the 15th International Joint Conf. on Artificial Intelligence, Volume one, 522–527, Morgan Kaufmann, 1997.
P. van Beek. Reasoning about qualitative temporal information. Artificial Intelligence, 58(1–3), 297–321, 1992.
M. Vilain, H. Kautz. Constraint propagation algorithms for temporal reasoning. AAAI-86. Proc. of the 5th National Conf. on Artificial Intelligence, 377–382, 1986.
M. Vilain, H. Kautz, P. van Beek. Constraint propagation algorithms for temporal reasoning: a revised report. D. Weld, J. de Kleer (editors), Qualitative Reasoning about Physical Systems, 373–381, Morgan Kaufman, 1989.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Balbiani, P., Condotta, JF., del Cerro, L.F. (1999). A Tractable Subclass of the Block Algebra: Constraint Propagation and Preconvex Relations. In: Barahona, P., Alferes, J.J. (eds) Progress in Artificial Intelligence. EPIA 1999. Lecture Notes in Computer Science(), vol 1695. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48159-1_6
Download citation
DOI: https://doi.org/10.1007/3-540-48159-1_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66548-9
Online ISBN: 978-3-540-48159-1
eBook Packages: Springer Book Archive