Non-primitive recursive decidability of products of modal logics with expanding domains

Annals of Pure and Applied Logic 142 (1):245-268 (2006)
  Copy   BIBTEX

Abstract

We show that—unlike products of ‘transitive’ modal logics which are usually undecidable—their ‘expanding domain’ relativisations can be decidable, though not in primitive recursive time. In particular, we prove the decidability and the finite expanding product model property of bimodal logics interpreted in two-dimensional structures where one component—call it the ‘flow of time’—is • a finite linear order or a finite transitive tree and the other is composed of structures like • transitive trees/partial orders/quasi-orders/linear orders or only finite such structures expanding over time. The decidability proof is based on Kruskal’s tree theorem, and the proof of non-primitive recursiveness is by reduction of the reachability problem for lossy channel systems. The result is used to show that the dynamic topological logic interpreted in topological spaces with continuous functions is decidable if the number of function iterations is assumed to be finite

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,150

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Decidable and undecidable logics with a binary modality.ágnes Kurucz, István Németi, Ildikó Sain & András Simon - 1995 - Journal of Logic, Language and Information 4 (3):191-206.
Modal Logics in the Vicinity of S.Brian F. Chellas & Krister Segerberg - 1996 - Notre Dame Journal of Formal Logic 37 (1):1-24.

Analytics

Added to PP
2013-12-31

Downloads
20 (#769,678)

6 months
11 (#241,037)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Two-dimensional modal logic.Krister Segerberg - 1973 - Journal of Philosophical Logic 2 (1):77 - 96.
Products of modal logics, part 1.D. Gabbay & V. Shehtman - 1998 - Logic Journal of the IGPL 6 (1):73-146.
Logics containing k4. part I.Kit Fine - 1974 - Journal of Symbolic Logic 39 (1):31-42.
Dynamic topological logic.Philip Kremer & Grigori Mints - 2005 - Annals of Pure and Applied Logic 131 (1-3):133-158.
Dynamic topological logic.Philip Kremer & Giorgi Mints - 2005 - Annals of Pure and Applied Logic 131 (1-3):133-158.

View all 20 references / Add more references