Joseph Y. Halpern
Yoav Shoham
- 1 ALLEN, J.F. Maintaining knowledge about temporal intervals. Commun. A CM, 26, 11 (Nov. 1983), 832-843. Google Scholar
- 2 ALLEN, J. F. Towards a general theory of action and time. Artif. Int. 23, 2 (July 1984), 123-154. Google Scholar
- 3 ALLEN, J. F. AND HAYES, P.J. A common-sense theory of time. In Proceedings of the 9th International Joint Conference on Artificial Intelligence (IJCAD (Los Angeles, Cahf.). Morgan Kaufmann, San Mateo, Calif., 1985~ pp. 528-531.Google Scholar
- 4 BARR~NGER, H., KUIPER, R., AND PNUELI, A. A really abstract concurrent model and its temporal logic. In Proceedings of 13th ACM Symposium on Principles of Programming Languages (St. Petersburg Beach, Fla., Jan. 13-15). ACM~ New York, 1986, pp. 173-183. Google Scholar
- 5 BURGESS, J.P. Axioms for tense logic II: Time periods. Notre Dame J. Formal Logic 23, 4 (Oct. 1982), 375-383.Google Scholar
- 6 BOBROW, D. G., ED. Special volume on qualitative reasoning and physical systems. Artif. Int. 24, 1-3 (Dec. 1984).Google Scholar
- 7 ENDERTON, H.B. A Mathematical Introduction to Logic. Academic Press, New York, 1972.Google Scholar
- 8 HALPERN, J. Y., MANNA, Z., AND MOSZKOWSKI, B. A high-level semantics based on interval logic. In Proceedings of the lOth International Colloquium on Automata, Languages, and Programming. Springer Verlag, New York, 1983, pp. 278-291. Google Scholar
- 9 HAMBLIN, C.L. Instants and intervals. Stud. Gen. 27, (1971), 127-134.Google Scholar
- 10 HAREL, D., PNUEH, A., AND STAW, Y. Propositional dynamic logic of nonregular programs. J. Comput. Syst. Sci. 26, 2 (1983), 222-243.Google Scholar
- 11 HAREL, D., KOZEN, D., AND PARIKH, R. Process logic: Expressiveness, decidability, completeness. J. Comput. Syst. Sci. 25, 2 (Oct. 1982), 145-180.Google Scholar
- 12 HUMBERSTONE, I. L. Interval semantics for tense logics: Some remarks J. Phdo. Logic 8 (1979), 171-196.Google Scholar
- 13 KOWALSK~, R., AND SERGOT, M. A logic-based calculus of events New Gen. Comput. 4 (1986), 67- 95. Google Scholar
- 14 LADKIN, P. The logac of time representation Ph.D dissertation Dept. Math., Univ. California, Berkeley, Berkeley, Cahf., 1988. Google Scholar
- 15 LADKIN, P., AND MADDUX, R The algebra of convex time intervals Unpublished manuscript. 1987.Google Scholar
- 16 MCDERMOTT, D. V. A temporal logic for reasoning about processes and plans. Cog. Sci. 6 (1982), 101-155.Google Scholar
- 17 MoszKowsr, J, B. C. Reasoning about digital circuits. Ph.D. dissertation. Comput Sci. Dept, Stanford Umv., Stanford, Cahf., July 1983. Google Scholar
- 18 NISHIMURA, H. Descriptwely complete process logic. Acta Inf. 14, 4 (1980), 359-369.Google Scholar
- 19 PARIKH, R. A decidability result for second order process logic. In Proceedmgs of the 19th Annual Symposium on Foundations of Computer Scwnce (Oct.). IEEE, New York, 1978, pp. 177-183.Google Scholar
- 20 PLAISTED, I). A Low-Level Language for Obtaining Decision Procedures for Classes of Temporal Logics. Sprlnger-Verlag, New York, 1984, pp. 403-420. Google Scholar
- 21 PNUF~L~, A. A temporal logic of programs. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science (Oct.). IEEE, New York, 1977, pp. 46-57.Google Scholar
- 22 PR~,TT, V.R. Semantical considerations on Floyd-Hoare logic In Proceedings of the 17th Annual Symposium on Foundatlons of Computer Science (Oct.). IEEE, New York, 1976, pp 109-121.Google Scholar
- 23 PRATT, V.R. Process logic. In Proceedings of the 6th Annual Symposium on the Principles of Programmmg Languages. ACM, New York, 1979, pp. 93-100. Google Scholar
- 24 PRIOR, A.N. Past, Present, and Future. Clarendon Press, Oxford, England, 1967.Google Scholar
- 25 RotoRs, JR., H. Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967.Google Scholar
- 26 ROPER, P. Intervals and tenses. J. Philo. Logic 9 (1980).Google Scholar
- 27 SCHW&RTZ, R. L., MELLIAR-SMITH, P. M , AND VOGT, F H. An interval logic for higher-level temporal reasoning. Computer Science Laboratory, SRI International, Menlo Park, Calif., 1983Google Scholar
- 28 SHOHAM, Y. Reasoning about Change. MIT Press, Boston, Mass., 1987.Google Scholar
- 29 SHOHAM Y. Temporal logics m AI. Semantical and ontological considerations. Artif. Int. 33 (1987), 89-I04. Google Scholar
- 30 STREF, TT, R S. Global process logic is H l-complete. Unpublished manuscript.Google Scholar
- 31 VAN BF, NTHEM, J. F. A.K. The Logic of Time. Reldel, Dororecht, The Netherlands, 1983Google Scholar
- 32 VAN BENTHEM, J. F. A. K. Time, logic and computation. In Lecture Notes m Computer Science, vol 354. Springer-Verlag, New York, 1989, pp. 1-49. Google Scholar
- 33 VENEMA, Y. Expressiveness and completeness of an interval tense logic. Tech. Rep. ITLI Prepubticatlon Series 88-02, University of Amsterdam, The Netherlands, 1988.Google Scholar
Index Terms
- A propositional modal logic of time intervals
Recommendations
Naming Worlds in Modal and Temporal Logic
In this paper we suggest adding to predicate modal and temporal logic a locality predicate W which gives names to worlds (or time points). We also study an equal time predicate D(x, y) which states that two time points are at the same distance from the ...
On Blass Translation for Leśniewski’s Propositional Ontology and Modal Logics
AbstractIn this paper, we shall give another proof of the faithfulness of Blass translation (for short, B-translation) of the propositional fragment of Leśniewski’s ontology in the modal logic by means of Hintikka formula. And we extend the result to ...
A modal logic internalizing normal proofs
In the proof-theoretic study of logic, the notion of normal proof has been understood and investigated as a metalogical property. Usually we formulate a system of logic, identify a class of proofs as normal proofs, and show that every proof in the ...
Reviews
Edward Sava-Segal
The modal temporal logic based on time intervals that Halpern and Shoham introduce is a generalization of point-based temporal logic. The need for assertions to refer to time intervals rather than time points emerged from artificial intelligence areas like qualitative physics and automatic planning, but this work is intended to be a general vehicle for representing temporal information in what would be considered in many situations a more natural way. Intervals are not defined as primitive objects, however; the authors extend the point-based modal temporal logic by simply replacing the notion of satisfaction by a state with the notion of satisfaction by an ordered pair of states. Syntax and semantics are defined both informally and formally. Halpern and Shoham use six modal operators to build well-formed formulas. The logic is general enough not to assume any connection between the truth value of a proposition over an interval and its truth value over any part of that interval. Even more interesting, the only assumption made with respect to the underlying temporal structure is that the set of time points that lie between two points is totally ordered. Other time constraints—discreteness, linearity, density, and completeness—are not imposed. Halpern and Shoham characterize the expressiveness of their logic by capturing the definition of those constraints in the logic itself. The issue of time structure proves to be extremely sensitive for the validity problem for this logic. The authors dedicate a full section of their paper to studying this problem for different time constraints, and they prove that for most interesting classes of temporal structures, validity and satisfiability are undecidable. Halpern and Shoham relate their work to other work in the field, especially process logic. Some previous knowledge of modal logics might be useful for fully understanding this valuable paper.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments