Skip to main content
SpringerLink
Log in

Quantification over Sets of Possible Worlds in Branching-Time Semantics

  • Published:
Studia Logica Aims and scope Submit manuscript

Abstract

Temporal logic is one of the many areas in which a possible world semantics is adopted. Prior's Ockhamist and Peircean semantics for branching-time, though, depart from the genuine Kripke semantics in that they involve a quantification over histories, which is a second-order quantification over sets of possible worlds. In the paper, variants of the original Prior's semantics will be considered and it will be shown that all of them can be viewed as first-order counterparts of the original semantics.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Barcellan, B. and A. Zanardo ‘Actual futures in peircean branching-time logic’, Vossiuspers, page /contribs/zanardo/, Amsterdam University Press, Amsterdam, 1999. ISBN 90 5629 104 1.

    Google Scholar 

  2. Bauer, S., I. Hodkinson, F. Wolter, and M. Zakharyaschev, ‘On non-local propositional and local one-variable quantified CTL*’, in M Fisher and A Artale, (eds.), Proc. 9th Internat. symposium on temporal representation and reasoning (TIME-2002), IEEE Inc, 2002, pp. 2–9.

  3. Belnap, N., M. Perloff, and M. Xu, Facing the Future. Agents and Choices in Our Indeterminst World, Oxford University Press, 2001.

  4. van Benthem, J.‘Temporal Logic’, in D. Gabbay, C. Hogger, and J. Robinson, (eds.), Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 4, Oxford University Press, 1995, pp. 241–350.

  5. van Benthem, J.‘Content versus wrapping: an essay in semantic complexity’, in M. Marx, L. Pólos, and M. Masuch, (eds.), Arrow Logic and Multi-Modal Logic, Studies in Logic, Language and Information, CSLI Publications, Stanford, 1996, pp. 203– 219.

    Google Scholar 

  6. van Benthem, J.‘Temporal patterns and modal structure’, Logic J. of the IGPL, 7(1):7–26, 1999. Special issue on Tempora Logic.

    Article  Google Scholar 

  7. Braüner, T., P. Hasle, and P. Øhrstrøm, ‘Ockhamistic logics and true futures of counterfactual moments’, in Proceedings of Fifth International Workshop on Temporal Representation and Reasoning (TIME 98), Sanibel Island, Florida, IEEE Press, 1998.

  8. Burgess, J., ‘The unreal future’, Theoria, 44:157–179, 1978.

    Article  Google Scholar 

  9. Burgess, J., ‘Logic and time’, J. of Symbolic Logic, 44:556–582, 1979.

    Article  Google Scholar 

  10. Burgess, J., ‘Decidability for branching time’, Studia Logica, 39:203–218, 1980.

    Article  Google Scholar 

  11. Chellas, B. Modal Logic: an introduction, Cambridge University Press, Cambridge, 1980.

    Google Scholar 

  12. Clark, E. E., and P. Sistla, ‘Automatic verification of finite state concurrent systems using temporal logic specifications’, ACM Transactions on Progamming Languages and Systems, 8:244–263, 1986.

    Article  Google Scholar 

  13. Emerson, E., and J. Halpern, ‘“Sometimes” and “not never” revisited: on branch-ing versus linear time temporal logic’, Journal ACM, 33(1):151–178, 1986.

    Article  Google Scholar 

  14. Gabbay, D. ‘An irreflexivity lemma with applications to axiomatizations of conditions on tense frames’, in U. Mönnich, (ed.), Aspects of Philosophical Logic, Reidel, Dordrecht, 1981, pp. 67–89.

    Google Scholar 

  15. Gabbay, D., I. Hodkinson, and M. Reynolds, Temporal Logic: Mathematical Foundation and Computational Aspects, vol.I. Oxford University Press, Oxford, 1994.

    Google Scholar 

  16. Gurevich, Y. and S. Shelah, ‘The decision problem for branching time logic’, J. of Symbolic Logic, 50(3):668–681, 1985.

    Article  Google Scholar 

  17. Henkin, L., ‘Completeness in the theory of types’, Journal of Symbolic Logic, 15:81– 91, 1950.

    Article  Google Scholar 

  18. Hodkinson, I., F. Wolter, and M. Zakharyaschev, ‘Decidable and undecidable fragments of first-order branching temporal logics’, in Proceedings of the IEEE Symposium on Logic in Computer Science (LICS), IEEE Computer Science Press, 2002.

  19. Laroussinie, F. and Ph. Schnoebelen, ‘Specification in CTL+past for verification in CTL’, Information and Computation, 156:236–263, 2000.

    Article  Google Scholar 

  20. Øhrstrøm, P., and P. F. V. Hasle, Temporal Logic: From Ancient Ideas to Arti-ficial Intelligence, Studies in Linguistic and Philosophy, Reidel, Dordrecht, 1995.

    Google Scholar 

  21. Prior, A., Past, Present and Future, Clarendon, Oxford, 1967.

    Google Scholar 

  22. Rabin, M., ‘Decidability of second order theories and automata on infinite trees’, Transaction of the American Mathematical Society, 141:1–35, 1966.

    Article  Google Scholar 

  23. Reynolds, M., ‘An axiomatization of PCTL*’, Information and Computation. To appear.

  24. Reynolds, M., ‘An axiomatization of full computation tree logic’, J. of Symbolic Logic, 66(3):1011–1057, 2001.

    Article  Google Scholar 

  25. Reynolds, M., ‘Axioms for branching-time’, J. of Logic and Computation, 12(4):679–697, 2002.

    Article  Google Scholar 

  26. Sabbadin, M., and A. Zanardo, ‘Topological aspects of branching-time semantics’, Studia Logica, 75:271–286, 2003.

    Article  Google Scholar 

  27. Segerberg, K., An Essay in Classical Modal Logic. Filosofiska Studier 13. University of Uppsala, 1971.

  28. Stirling, C., ‘Modal and temporal logics’, in S. Abramsky, D. Gabbay, and T. Maibaum, (eds.), Handbook of Logic in Computer Science, Oxford University Press, 1991.

  29. Thomason, R., ‘Combination of tense and modality’, in D. Gabbay and F. Guenthner, (eds.), The Handbook of Philosophical Logic, volume II, chapter 3, Reidel, Dordrecht, 1984, pp. 135–165.

    Google Scholar 

  30. Wölfl, S., ‘Combinations of tense and modality for predicate logic’, J. of Philosophical Logic, 28:371–398, 1999.

    Article  Google Scholar 

  31. Wölfl, S., Kombinierte Zeit und Modallogik: Vollständigkeitsresultate für prädikatenlogische Sprachen. Logische Philosophie: 5. Logos Verlag, Berlin, 1999.

    Google Scholar 

  32. Wölfl, S., ‘Propositional Q-logic’, J. of Philosophical Logic, 31:387–414, 2002.

    Article  Google Scholar 

  33. Wooldridge, M., and M. Fisher, ‘A first-order branching time logic of multiagent systems’, in B. Neumann, (ed.), Proc. 10th European Conference on Artificial Intelligence (ECA192), John Wiley and Sons, Chichester, 1992, pp. 234–238.

    Google Scholar 

  34. Zanardo, A., ‘A finite axiomatization of the set of strongly valid ockhamist formulas’, J. of Philosophical Logic, 14:447–468, 1985.

    Article  Google Scholar 

  35. Zanardo, A., ‘Axiomatization of ‘Peircean’ Branching-Time Logic’, Studia Logica, 49(2):183–195, 1990.

    Article  Google Scholar 

  36. Zanardo, A., ‘Branching-time logic with quantification over branches: the point of view of modal logic’, J. of Symbolic Logic, 61(1):1–39, 1996.

    Article  Google Scholar 

  37. Zanardo, A., ‘Branching-time as a relative closeness relation among histories’, in R. Asatiani, K. Balogh, G. Chikoidze, P. Dekker, and D. de Jongh, (eds.), Proceedings of the Fifth Tbilisi Symposium on Language, Logic and Computation, October 6–10, 2003, ILLC, University of Amsterdam, CLLS, Tbilisi State University, 2004, pp. 11–18.

  38. Zanardo, A., ‘Moment/History Duality in Prior’s Logics of Branching-Time’, in T. Braüner, P. Hasle, and P. Øhrstrøm, (eds.), The logic of Time and Modality. To appear in Synthese.

  39. Zanardo, A., and J. Carmo, ‘Ockhamist computational logic: Past-sensitive necessitation in CTL*’, J. of Logic and Computation, 3(3):249–268, 1993.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Matematica Pura ed Applicata, Via Belzoni, 7-3513, Padova, Italy

    Alberto Zanardo

Authors
  1. Alberto Zanardo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alberto Zanardo.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zanardo, A. Quantification over Sets of Possible Worlds in Branching-Time Semantics. Stud Logica 82, 379–400 (2006). https://doi.org/10.1007/s11225-006-8104-z

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11225-006-8104-z

Keywords

Search

Navigation