Algorithmic problems concerning first-order definability of modal formulas on the class of all finite frames

Studia Logica 55 (3):421 - 448 (1995)
  Copy   BIBTEX

Abstract

The main result is that is no effective algorithmic answer to the question:how to recognize whether arbitrary modal formula has a first-order equivalent on the class of finite frames. Besides, two known problems are solved: it is proved algorithmic undecidability of finite frame consequence between modal formulas; the difference between global and local variants of first-order definability of modal formulas on the class of transitive frames is shown.

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 102,217

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

Definability in the class of all -frames – computability and complexity.D. T. Georgiev - 2017 - Journal of Applied Non-Classical Logics 27 (1-2):1-26.
Modal characterisation theorems over special classes of frames.Anuj Dawar & Martin Otto - 2010 - Annals of Pure and Applied Logic 161 (1):1-42.
Elementary Canonical Formulae: A Survey on Syntactic, Algorithmic, and Modeltheoretic Aspects.W. Conradie, V. Goranko & D. Vakarelov - 1998 - In Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev (eds.), Advances in Modal Logic. CSLI Publications. pp. 17-51.
Existential definability of modal frame classes.Tin Perkov & Luka Mikec - 2020 - Mathematical Logic Quarterly 66 (3):316-325.
Sahlqvist Formulas Unleashed in Polyadic Modal Languages.Valentin Goranko & Dimiter Vakarelov - 1998 - In Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev (eds.), Advances in Modal Logic. CSLI Publications. pp. 221-240.
Hybrid Formulas and Elementarily Generated Modal Logics.Ian Hodkinson - 2006 - Notre Dame Journal of Formal Logic 47 (4):443-478.

Analytics

Added to PP
2009-01-28

Downloads
65 (#333,844)

6 months
11 (#303,323)

Historical graph of downloads
How can I increase my downloads?