Abstract
Concurrent systems are subject to a form of temporal uncertainty due to the non-deterministic order of execution. Distributed systems cause additional uncertainty by the lack of a common clock and the communication delays. Adequate methods for checking the specification and design of such systems must allow for sound reasoning about asynchronous activities, while automated methods should perform the reasoning in polynomial time. This paper presents the basis for such deductive systems through a very general temporal relation algebra which can be used with constraint propagation techniques. Based on intervals in relativistic space-time, it naturally incorporates the expression of uncertain and ambiguous temporal relations, as well as concurrent actions. The possible temporal relations are analyzed and named consistently with earlier work of the authors, followed by an explanation of the calculation of compositions of the atomic temporal relations. The resulting table of compositions is the cornerstone of a temporal constraint-based reasoner that presently supports a prototype concurrent system debugger by deducing from partial run-time information the existence of temporal behavior inconsistent with specifications.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abraham, U., Ben-David, S. & Magidor, M. On Global-Time Interprocess Communication. In Semantics for Concurrency, M. Kwiatkowska, M. Shields & R. Thomas, eds., Springer-Verlag, Leicester, 1990.
Allen, J. Maintaining Knowledge about Temporal Intervals. Comm. of ACM 26, 11 (1983), pp. 832–843.
Anger, F. On Lamport's Interprocessor Communication Model. ACM Trans. on Prog. Lang. and Systems 11, 3 (July 1989), pp. 404–417.
Anger, F., Rodriguez, R., and Hadlock, F. Temporal Consistency Checking of Natural Language Specifications. Applications of Artificial Intelligence VIII, SPIE, Orlando, (April 1991), pp. 572–580.
Anger, F., Ladkin, P. & Rodriguez, R. Atomic Temporal Interval Relations in Branching Time: Calculation and Application. Applications of AI IX, SPIE, Orlando, (April 1991), pp. 122–136.
Anger, F. and Rodriguez, R. Time, Tense, and Relativity Revisited. In Lecture Notes in Computer Science, Bouchon-Meunier, B., Yager, R., and Zadeh, L., eds, Springer-Verlag, Heidelberg, Germany, 1991, pp. 286–295.
Goldblatt, R. Diodorean Modality in Minkowski Spacetime. Studia Logica 39, 2/3 (1980), pp. 219–236.
Lamport, L. The Mutual Exclusion Problem: Part I-A Theory of Interprocess Communication. Journal ACM 33, 2 (April 1986), pp. 313–326.
Manna, Z. and Wolper, P. Synthesis of Communication Processes from Temporal Logic Specifications. ACM Trans. Prog. Lang. & Syst. 6, 1 (Jan.1984), pp. 68–93.
Pelavin R. and Allen, J. A Model for Concurrent Actions having Temporal Extent. Proceedings of the Sixth National Conference on Artificial Intelligence, Seattle, WA, (July 1987), pp. 246–250.
Pnueli, A. The Temporal Semantics of Concurrent Programs. Proceedings of the 18th Symposium on the Foundations of Computer Science, IEEE, Providence, (Nov 1977), pp. 46–57.
Rodriguez, R., Anger, F., and Ford, K. Temporal Reasoning: A Relativistic Model. International Journal of Intelligent Systems 6, (Jun 1991), pp. 237–254.
Rodriguez, R., Anger, F., and Walrath, G. Implementation Aspects of a Minimally Intrusive Debugger for Concurrent Systems. Software Engineering Research Forum, Melbourne FL (Nov 1992), pp. 223–231.
Rodriguez, R. A Relativistic Temporal Algebra for Efficient Design of Distributed Systems. Journal of Applied Intelligence 3, 1 (1993), pp. 31–45.
Rodriguez, R. and Anger, F. Prior's Legacy in Computer Science. In Logic and Reality: Essays in Pure and Applied Logic, In Memory of Arthur Prior, J. Copeland, ed., Oxford University Press, Oxford, 1993.
van Beek, P. Approximation Algorithms for Temporal Reasoning. In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, (1989), pp. 1291–1296.
van Beek, P. Exact and Approximate Reasoning about Qualitative Temporal Relations. PhD Thesis, University of Alberta, 1990.
van Benthem, J. A Manual of Intensional Logic, CSLI/SRI International, Menlo Park, CA, 1988.
Vilain, M. and Kautz, H. Constraint Propagation Algorithms for Temporal Reasoning. Proceedings of the Fifth National Conference of AAAI, Pittsburgh, PA, (Aug 1986), pp. 377–382.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag
About this paper
Cite this paper
Rodriguez, R.V., Anger, F.D. (1993). An analysis of the temporal relations of intervals in relativistic space-time. In: Bouchon-Meunier, B., Valverde, L., Yager, R.R. (eds) IPMU '92—Advanced Methods in Artificial Intelligence. IPMU 1992. Lecture Notes in Computer Science, vol 682. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56735-6_51
Download citation
DOI: https://doi.org/10.1007/3-540-56735-6_51
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56735-6
Online ISBN: 978-3-540-47643-6
eBook Packages: Springer Book Archive