Skip to main content
SpringerLink
Log in

A System of Dynamic Modal Logic

  • Published:
Journal of Philosophical Logic Aims and scope Submit manuscript

Abstract

In many logics dealing with information one needs to make statements not only about cognitive states, but also about transitions between them. In this paper we analyze a dynamic modal logic that has been designed with this purpose in mind. On top of an abstract information ordering on states it has instructions to move forward or backward along this ordering, to states where a certain assertion holds or fails, while it also allows combinations of such instructions by means of operations from relation algebra. In addition, the logic has devices for expressing whether in a given state a certain instruction can be carried out, and whether that state can be arrived at by carrying out a certain instruction.

This paper deals mainly with technical aspects of our dynamic modal logic. It gives an exact description of the expressive power of this language; it also contains results on decidability for the language with ‘arbitrary’ structures and for the special case with a restricted class of admissible structures. In addition, a complete axiomatization is given. The paper concludes with a remark about the modal algebras appropriate for our dynamic modal logic, and some questions for further work.

The paper only contains some sketchy examples showing how the logic can be used to capture situations of dynamic interest, far more detailed applications are given in a companion to this paper (De Rijke [33]).

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.

Institutional subscriptions

Similar content being viewed by others

REFERENCES

  1. Alchourrón, C., Gärdenfors, P. and Makinson, D. (1985): On the logic of theory change. Journal of Symbolic Logic 50: 510- 530.

    Google Scholar 

  2. Andréka, H., Kurucz, Á., Németi, I., Sain, I. and Simon, A. (1996): Exactly which logics touched by the dynamic trend are decidable? In L. Pólós, M. Masuch, M. Marx (eds.), Arrow Logics and Multi-Modal Logics, Studies in Logic, Language and Information, CSLI Publications.

  3. Van Benthem, J. (1983): Modal Logic and Classical Logic. Bibliopolis, Naples.

    Google Scholar 

  4. Van Benthem, J. (1989): Modal logic as a theory of information. Technical Report LP-89-05, ILLC, University of Amsterdam.

    Google Scholar 

  5. Van Benthem, J. (1991): Language in Action. Nort-Holland, Amsterdam.

    Google Scholar 

  6. Van Benthem, J. (1900): Logic and the flow of information. In D. Prawitz, B. Skyrms and D. Westerståhl (eds.), Proc. 9th ILMPS, North-Holland, Amsterdam.

    Google Scholar 

  7. Brink, C. (1981): Boolean modules. Journal of Algebra 71: 291- 313.

    Google Scholar 

  8. Brink, C., Britz, K. and Schmidt, R. (1994): Peirce algebras. Formal Aspects of Computing 6: 339- 358.

    Google Scholar 

  9. Danecki, R. (1985): Nondeterministic propositional dynamic logic with intersection is decidable. In LNCS 208, Springer, New York, pp. 34- 53.

    Google Scholar 

  10. Van Eijck, J. and de Vries, F.-J. (1995): Reasoning about update logic. Journal of Philosophical Logic 24: 19- 46.

    Google Scholar 

  11. Finger, M. and Gabbay, D. M. (1992): Adding a temporal dimension to a logic system. Journal of Logic, Language and Information 1: 203- 233.

    Google Scholar 

  12. Fuhrmann, A. (1990): On the modal logic of theory change. In A. Fuhrmann and M. Morreau (eds.), LNAI 465, pp. 259- 281.

  13. Gabbay, D. M. and Hodkinson, I. M. (1991): An axiomatization of the temporal logic with Since and Until over the real numbers. Journal of Logic and Computation 1: 229- 259.

    Google Scholar 

  14. Gabbay, D. M., Hodkinson, I. and Reynolds, M. (1994): Temporal Logic: Mathematical Foundations and Computational Aspects. Oxford University Press, Oxford.

    Google Scholar 

  15. Gärdenfors, P. (1988): Knowledge in Flux. The MIT Press, Cambridge, MA.

    Google Scholar 

  16. Gargov, G. and Passy, S. (1990): A note on Boolean modal logic. In Petkov, P. P. (ed.), Mathematical Logic. Proccedings of the 1988 Heyting Summerschool, Plenum Press, New York, 311- 321.

    Google Scholar 

  17. Groenendijk, J. and Stokhof, M. (1991): Dynamic predicate logic. Linguistics and Philosophy 14: 39- 100.

    Google Scholar 

  18. Gurevich, Y. and Shelah, S. (1985): The decision problem for branching time logic. Journal of Symbolic Logic 50: 668- 681.

    Google Scholar 

  19. Harel, D. (1983): Recurring dominoes: making the highly undecidable highly understandable. In LNCS 158 (Proc. of the Conference on Foundations of Computing Theory), pp. 177- 194. Springer-Verlag, Berlin.

    Google Scholar 

  20. Harel, D. (1984): Dynamic Logic. In Gabbay, D. M. and Guenthner, F. (eds.), Handbook of Philosophical Logic, vol. 2, Reidel, Dordrecht, pp. 497- 604.

    Google Scholar 

  21. Jaspars, J. (1994): Calculi for Constructive Communicaton. Ph.D. thesis. ITK, Tilburg, and ILLC, University of Amsterdam.

    Google Scholar 

  22. Jaspars, J. and Krahmer, E. (1996): A programme of modal unification of dynamic theories. In Proceedings of the 10th Amsterdam Colloquium, ILLC, University of Amsterdam.

    Google Scholar 

  23. Kamp, H. (1968): Tense Logic and the Theory of Linear Order. Ph.D. thesis, UCLA.

  24. Katsuno, H. and Mendelzon, A. O. (1991): On the difference between updating a knowledge base and revising it. In Allen, J. A., Fikes, R. and Sandewall, E. (eds.), Princ. of Knowledge Representation and Reasoning: Proc. 2nd Intern. Conf., pp. 387- 394. Morgan Kaufman.

  25. Katsuno, H. and Mendelzon, A. O. (1992): Propositional knowledge base revision and minimal change. Artificial Intelligence 52: 263- 294.

    Google Scholar 

  26. Kozen, D. (1981): On the duality of dynamic algebras and Kripke models. In Engeler, E. (ed.), Logic of Programs 1981, LNCS 125, pp. 1- 11. Springer-Verlag, Berlin.

    Google Scholar 

  27. Marx, M. (1995): Algebraic Relativization and Arrow Logic. Ph.D. thesis, ILLC, University of Amsterdam.

    Google Scholar 

  28. Passy, S. and Tinchev, T. (1991): An essay in combinatory dynamic logic. Information and Computation 93: 263- 332.

    Google Scholar 

  29. Pratt, V. (1990): Action logic and pure induction. In van Eijck, J. (ed.), JELIA-90, pp. 97- 120, Springer-Verlag, Berlin.

    Google Scholar 

  30. Pratt, V. (1990): Dynamic algebras as a well-behaved fragment of relation algebras. In Bergman, C. H., Maddux, R. D. and Pigozzi, D. L. (eds.), Algebraic Logic and Universal Algebra in Computer Science, LNCS 425, pp. 77- 110.

  31. Rabin, M. O. (1969): Decidability of second order theories and automata on infinite trees. Transactions of the American Mathematical Society 141: 1- 35.

    Google Scholar 

  32. De Rijke, M. (1992): The modal logic of inequality. Journal of Symbolic Logic 57: 566- 584.

    Google Scholar 

  33. De Rijke, M. (1994): Meeting some neighbours. In van Eijck, J. and Visser, A. (eds.), Logic and Information Flow, MIT Press, Cambridge, Mass., pp. 170- 195.

    Google Scholar 

  34. De Rijke, M. (1995): The logic of Peirce algebras. Journal of Logic, Language and Information 4: 227- 250.

    Google Scholar 

  35. De Rijke, M. (1995): Modal model theory. Report CS-R9517, CWI, Amsterdam. To appear in Annals of Pure and Applied Logic.

    Google Scholar 

  36. Veltman, F. (1996): Defaults in update semantics. Journal of Philosophical Logic 25: 221- 261.

    Google Scholar 

  37. Venema, Y. (1991): Many-Dimensional Modal Logic. Ph.D. Thesis, ILLC, University of Amsterdam.

    Google Scholar 

  38. Venema, Y. (1993): Derivation rules as anti-axioms in modal logic. Journal of Symbolic Logic 58: 1003- 1034.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Warwick, Coventry, CV4 7AL, U.K. (email

    Maarten de Rijke

Authors
  1. Maarten de Rijke
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

de Rijke, M. A System of Dynamic Modal Logic. Journal of Philosophical Logic 27, 109–142 (1998). https://doi.org/10.1023/A:1004295308014

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1004295308014

Keywords

Search

Navigation