Systems of temporal logic: moments, histories, trees

##plugins.themes.bootstrap3.article.main##

Oleg M. Grigoriev

Abstract

The article is intended to give a review of the basic ideas underlying the semantic constructions which are used in different systems of $\textit{logic of time}$ viewed as one of the branches of contemporary philosophical logic. For the systems of linear and branching time the key features of their formalized languages are discussed along with model structures used for the purposes of their interpretation. The links to the main technical results concerning the formalizations of that systems are also given.

##plugins.generic.usageStats.downloads##

##plugins.generic.usageStats.noStats##

##plugins.themes.bootstrap3.article.details##

Section
Analitycal overviews

References

Allen, 1984 – Allen J.F. Towards a General Theory of Action and Time // Artificial Intelligence. 1984. Vol. 23. P. 123–154.
Allen, Ferguson, 1994 – Allen, J.F., Ferguson G. Actions and Events in Interval Temporal Logic // Journal of Logic and Computation. 1994. Vol. 4. No. 5. P. 531–579.
van Benthem, 1983 – van Benthem J. The Logic of Time. Dordrecht; Boston; London: Kluwer Academic Publishers, 1983.
van Benthem, 1995 – van Benthem J. Temporal logic // D.M. Gabbay, C.J. Hogger, and J.A. Robinson (eds.). Handbook of Logic in Artificial Intelligence and Logic Programming: Epistemic and Temporal Reasoning. Vol. 4. Oxford: Oxford University Press, 1995. P. 241–351.
Belnap, 1991 – Belnap N. Before refraining: Concepts for agency // Erkenntnis. 1991. Vol. 34. P. 137–169.
Belnap, Green, 1994 – Belnap N., Green M. Indeterminism and the thin red line // Philosophical Perspectives. 1994. Vol. 8. P. 365–388.
Belnap et al., 2001 – Belnap N., Perloff M., Xu M. Facing the future: Agents and choices in our indeterministic world. Oxford: Oxford University Press, 2001.
Belnap, 2005 – Belnap N. A theory of causation: Causae causantes (originating causes) as inus conditions in branching space-times // British Journal for the Philosophy of Science. 2005. Vol. 56. No. 2. P. 221–253.
Belnap et al., 2021 – Belnap N., M¨uller T., Placek T. New Foundations for Branching Space-Times // Studia Logica. 2021. Vol. 109. P. 239–284.
Blackburn et al., 2006 – Blackburn P., van Benthem J., Wolter F. Handbook of Modal Logics. Amsterdam: Elsevier, 2006.
Blackburn et al., 2002 – Blackburn P., de Rijke M., Venema Y. Modal Logic. Cambridge: Cambridge University Press, 2002.
Blackburn et al., 2019 – Blackburn P., Hasle P., Øhrstrøm P. (eds.). Logic and Philosophy of Time: Further Themes from Prior. Vol. 2. Aalborg: Aalborg Universitetsforlag, 2019. 230 p.
Burgess, 1978 – Burgess J. The Unreal Future // Theoria. 1978. Vol. 44. No. 3. P. 157–179.
Burgess, 1979 – Burgess J. Logic and Time // Journal of Symbolic Logic. 1979. Vol. 44. P. 566–582.
Burgess, 1980 – Burgess J. Decidability for Branching Time // Studia Logica. 1980. Vol. 39. P. 203–218.
Burgess, 1982 – Burgess J. Axioms for Tense Logic I: ‘Since’ and ‘Until’ // Notre Dame Journal of Formal Logic. 1982. Vol. 23. P. 367–374.
Burgess, 2002 – Burgess J. Basic Tense Logic // D.M. Gabbay and F. Guenthner (eds.). Handbook of Philosophical Logic. Vol. 7. Springer, 2002. P. 1–42.
Correia, Iacona, 2013 – Correia F., Iacona F. (eds.) Around the Tree: Semantic and Metaphysical Issues Concerning Branching and the Open Future. Synthese Library. Vol. 361. Dordrecht: Springer, 2013.
Demri et al., 2016 – Demri S., Goranko V., Lange M. Temporal Logics in Computer Science. Cambridge: Cambridge University Press, 2016.
Emerson, 1990 – Emerson E. Temporal and modal logics // J. van Leeuwen (ed.). Handbook of Theoretical Computer Science. Amsterdam: Elsevier, 1990. P. 995–1072.
Fisher et al., 2005 – Fisher M., Gabbay D., Vila L. Handbook of Temporal Reasoning in Artificial Intelligence. Amsterdam: Elsevier, 2005.
Gabbay et al., 1980 – Gabbay D., Pnueli A., Shelah S., Stavi J. On the temporal analysis of fairness // Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL ’80). Association for Computing Machinery. New York, 1980. P. 163–173.
Gabbay, 1981 – Gabbay D. An irreflexivity lemma with applications to axiomatizations of conditions on tense frames // U. M¨onnich (ed.). Aspects of Philosophical Logic. Reidel; Dordrecht, 1981. P. 67–89.
Gabbay et al., 1994 – Gabbay D., Hodkinson I., Reynolds M. Temporal Logic: Mathematical Foundations and Computational Aspects. Vol. 1. Oxford: Clarendon Press, 1994.
Galton, 1987 – Galton A.P. Temporal Logics and their Applications. London: Academic Press, 1987.
Goldblatt, 1992 – Goldblatt R. Logics of Time and Computation. (CSLI Lecture Notes 7.) Second Edition. Stanford: CSLI Publications, 1992.
Goranko, Rumberg, 2020 – Goranko V., Rumberg A. Temporal Logic // The Stanford Encyclopedia of Philosophy (Summer 2020 Edition). E.N. Zalta (ed.). https:// plato.stanford.edu/archives/sum2020/entries/logic-temporal/ Gurevich, Shelah, 1985 – Gurevich Y., Shelah S. The Decision Problem for Branching Time Logic // Journal of Symbolic Logic. 1985. Vol. 50. P. 668–681.
Hajnicz, 1996 – Hajnicz E. Time Structures. Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence). Vol. 1047. Springer, 1996.
Hasle et al., 2017 – Hasle P., Blackburn P.R., Øhrstrøm P. (eds.). Logic and Philosophy of Time: Themes from Prior. Vol. 1. Aalborg: Aalborg Universitetsforlag, 2017.
Kr¨oger, Merz, 2008 – Kr¨oger F., Merz S. Temporal Logic and State Systems. Texts in Theoretical Computer Science (An EATCS Series). Springer, 2008. Lichtenstein et al., 1985 – Lichtenstein O., Pnueli A., Zuck L.D. The glory of the past // Proceedings the Conference on Logic of Programs. London: SpringerVerlag, 1985. P. 196–218.
Kamp, 1968 – Kamp H. Tense Logic and the Theory of Linear Order. PhD Thesis. Los Angeles: University of California, 1968.
McArthur, 1976 – McArthur R. Tense Logic. Springer, Synthese Library, 1976. 91 p. M¨uller, 2010 – M¨uller T. Towards a theory of limited indeterminism in branching space-times // Journal of Philosophical Logic. 2010. Vol. 39. P. 395–423.
M¨uller, 2014 – M¨uller T. Alternatives to histories? Employing a local notion of modal consistency in branching theories // Erkenntnis. 2014. No. 79. P. 343–364. Øhrstrøm, 2009 – Øhrstrøm P. In Defence of the Thin Red Line: A Case for Ockhamism // Humana.mente. 2009. No. 8. P. 17–32.
Øhrstrøm, 1995 – Øhrstrøm P., Hasle P. Temporal Logic: From Ancient Ideas to Artificial Intelligence. Dordrecht: Kluwer Academic Publishers, 1995.
Øhrstrøm, 2006 – Øhrstrøm P., Hasle P. Modern Temporal Logic: The Philosophical Background // Handbook of the History of Logic. Vol. 7. 2006. P. 447–498. Pnueli, 1977 – Pnueli A. The Temporal Logic of Programs // Proceedings of the 18th IEEE Symposium on Foundations of Computer Science. 1977. P. 46–67.
Prior, 1957 – Prior A. Time and Modality. Oxford: Oxford University Press, 1957. Prior, 1967 – Prior A.N. Past, Present and Future. Oxford: Oxford University Press, 1967.
Rescher, 1971 – Rescher N., Urquhart A. Temporal Logic. Berlin: Springer, 1971.
Reynolds, 1992 – Reynolds M. An axiomatization for Until and Since over the reals without the IRR rule // Studia Logica. 1992. Vol. 51. P. 165–193.
Reynolds, 1994 – Reynolds M. Axiomatizing U and S over Integer Time // D. Gabbay, H. Ohlbach (eds.). Temporal Logic. Proceedings of the First International Conference ICTL. (Lecture Notes in Artificial Intelligence: Vol. 828.) Berlin; Heidelberg: Springer, 1994. P. 117–132.
Reynolds, 1997 – Reynolds M. A Decidable Temporal Logic of Parallelism // Notre Dame Journal of Formal Logic. 1997. Vol. 38. No. 3. P. 419–436.
Reynolds, 2001 – Reynolds M. An Axiomatization of Full Computation Tree Logic // Journal of Symbolic Logic. 2001. Vol. 66. P. 1011–1057.
Reynolds, 2002 – Reynolds M. Axioms for Branching Time // Journal of Logic and Computation. 2002. Vol. 12. No. 4. P. 679–697.
Reynolds, 2003 – Reynolds M. An Axiomatization of Prior’s Ockhamist Logic of Historical Necessity // Balbiani et al. (eds.) Advances in Modal Logic. Vol. 4. London: College Publications, 2003. P. 355–370.
Rumberg, 2016a – Rumberg A. Transition Semantics for Branching Time // Journal of Logic Language and Information. 2016. Vol. 25. P. 77–108.
Rumberg, 2019 – Rumberg A., Zanardo A. First-Order Definability of Transition Structures // Journal of Logic, Language and Information. 2019. Vol. 28. No. 3. P. 459–488.
Tarski, 1935 – Tarski A. Der Wahrheitsbegriff in den formalisierten Sprachen. // Studia Philosophica. 1935. Vol. 1. P. 261–405. (English translation: Tarski A. The Concept of Truth in Formalized Languages // Logic, Semantics, Metamathematics. Ed. by J. Corcoran. Second edition. Indianapolis: Hackett, 1983.)
Thomason, 1970 – Thomason R.H. Indeterminist Time and Truth-Value Gaps // Theoria. 1970. Vol. 36. No. 3. P. 264–281.
Thomason, 1984 – Thomason R.H. Combinations of Tense and Modality // D. Gabbay, F. Guenther (eds.). Handbook of Philosophical Logic (Extensions of Classical Logic: Volume 2). Dordrecht: Reidel, 1984. P. 135–165.
Thomason, 2020 – Thomason R.H. Logic and Artificial Intelligence // The Stanford Encyclopedia of Philosophy (Summer 2020 Edition). E.N. Zalta (ed.). https:// plato.stanford.edu/archives/sum2020/entries/logic-ai/
Venema, 1993 – Venema Y. Completeness via Completeness: Since and Until // M. de Rijke (ed.). Diamonds and Defaults. Dordrecht: Kluwer, 1993. P. 279–286.
Wawer, 2014 – Wawer J. The Truth About the Future // Erkenntnis. 2014. Vol. 79. P. 365–401.
Xu, 1988 – Xu M. On some U, S-Tense Logics // Journal of Philosophical Logic. 1988. Vol. 17. P. 181–202.
Zanardo, 1985 – Zanardo A. A finite axiomatization of the set of strongly valid Ockhamist formulas // Journal of Philosophical Logic. 1985. Vol. 14. P. 447–468.
Zanardo, 1990 – Zanardo A. Axiomatization of ‘Peircean’ branching-time logic // Studia Logica. 1990. Vol. 49. No. 2. P. 183–195.
Zanardo, 1996 – Zanardo A. Branching-time logic with quantification over branches: The point of view of modal logic // The Journal of Symbolic Logic. 1996. Vol. 61. No. 1. P. 1–39.
Zanardo, 1998 – Zanardo A. Undivided and Indistinguishable Histories in BranchingTime Logics // Journal of Logic, Language and Information. 1998. Vol. 7. P. 297–315.
Zanardo, 2003 – Zanardo A. First-Order and Second-Order Aspects of BranchingTime Semantics. Preprint Dipartimento di Matematica Universit`a di Padova. No. 3, 17 febbraio 2003.
Zanardo, 2006a – Zanardo A. Moment/history duality in Prior’s logics of branching time // Synthese. 2006. Vol. 150. No. 3. P. 483–507.
Zanardo, 2006b – Zanardo A. Quantification over sets of possible worlds in branchingtime semantics // Studia Logica. 2006. Vol. 82. No. 3. P. 379–400.