Definability in the class of all -frames – computability and complexity

Journal of Applied Non-Classical Logics 27 (1-2):1-26 (2017)
  Copy   BIBTEX

Abstract

In the basic modal language and in the basic modal language with the added universal modality, first-order definability of all formulas over the class of all frames is shown. Also, it is shown that the problems of modal definability of first-order sentences over the class of all frames in the languages and are both PSPACE-complete.

Categories

Keywords

Reprint years

DOI

10.1080/11663081.2017.1354498

Links

PhilArchive



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

External links

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

Through your library

My notes

Similar books and articles

Algorithmic problems concerning first-order definability of modal formulas on the class of all finite frames.A. V. Chagrov & L. A. Chagrova - 1995 - Studia Logica 55 (3):421 - 448.
Term Definable Classes of Boolean Functions and Frame Definability in Modal Logic.Miguel Couceiro, Lauri Hella & Jari Kivelä - 2008 - Logic Journal of the IGPL 16 (1):43-73.
Completeness and Definability in the Logic of Noncontingency.Evgeni E. Zolin - 1999 - Notre Dame Journal of Formal Logic 40 (4):533-547.
On the Modal Logic of Subset and Superset: Tense Logic over Medvedev Frames.Wesley H. Holliday - 2017 - Studia Logica 105 (1):13-35.
Characterizations of negative definability in modal logic.Marco Hollenberg - 1998 - Studia Logica 60 (3):357-386.
On definability in multimodal logic.Joseph Y. Halpern, Dov Samet & Ella Segev - 2009 - Review of Symbolic Logic 2 (3):451-468.
Barwise's information frames and modal logics.Vladimir V. Rybakov - 2003 - Archive for Mathematical Logic 42 (3):261-277.
Elementary definability and completeness in general and positive modal logic.Ernst Zimmermann - 2003 - Journal of Logic, Language and Information 12 (1):99-117.
A General Lindström Theorem for Some Normal Modal Logics.Sebastian Enqvist - 2013 - Logica Universalis 7 (2):233-264.
On definability in multimodal logic: On definability in multimodal logic.Joseph Y. Halpern - 2009 - Review of Symbolic Logic 2 (3):451-468.
On axiomatising products of Kripke frames.Ágnes Kurucz - 2000 - Journal of Symbolic Logic 65 (2):923-945.
On Axiomatising Products of Kripke Frames.Agnes Kurucz - 2000 - Journal of Symbolic Logic 65 (2):923-945.
A Unified Semantics for a Family of Modal Logics with Propositional Constants.Matteo Pascucci - 2016 - Logica Universalis 10 (1):45-66.
Modal sequents and definability.Bruce M. Kapron - 1987 - Journal of Symbolic Logic 52 (3):756-762.
Hybrid Formulas and Elementarily Generated Modal Logics.Ian Hodkinson - 2006 - Notre Dame Journal of Formal Logic 47 (4):443-478.

Analytics

Added to PP
2017-07-21

Downloads
38 (#429,640)

6 months
4 (#846,927)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Knowledge and belief.Jaakko Hintikka - 1962 - Ithaca, N.Y.,: Cornell University Press.
Modal Logic: Graph. Darst.Patrick Blackburn, Maarten de Rijke & Yde Venema - 2001 - New York: Cambridge University Press. Edited by Maarten de Rijke & Yde Venema.
Mathematical logic.Joseph R. Shoenfield - 1967 - Reading, Mass.,: Addison-Wesley.
An essay in classical modal logic.Krister Segerberg - 1971 - Uppsala,: Filosofiska föreningen och Filosofiska institutionen vid Uppsala universitet.

View all 19 references / Add more references