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

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

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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2006.01.001
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 41,507
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Products of Modal Logics, Part 1.D. Gabbay & V. Shehtman - 1998 - Logic Journal of the IGPL 6 (1):73-146.
Two-Dimensional Modal Logic.Krister Segerberg - 1973 - Journal of Philosophical Logic 2 (1):77 - 96.
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.
Logics Containing K4. Part I.Kit Fine - 1974 - Journal of Symbolic Logic 39 (1):31-42.

View all 19 references / Add more references

Citations of this work BETA

Dynamic Topological Logic Interpreted Over Minimal Systems.David Fernández-Duque - 2011 - Journal of Philosophical Logic 40 (6):767-804.

Add more citations

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 index
2013-12-31

Total views
4 ( #1,068,646 of 2,248,762 )

Recent downloads (6 months)
2 ( #795,663 of 2,248,762 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature