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

Studia Logica 55 (3):421 - 448 (1995)
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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1007/BF01057806
Options
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history
Request removal from index
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 26,162
Through your library
References found in this work BETA
Logical Constants Across Varying Types.Johan van Benthem - 1989 - Notre Dame Journal of Formal Logic 30 (3):315-342.
First-Order Definability in Modal Logic.R. I. Goldblatt - 1975 - Journal of Symbolic Logic 40 (1):35-40.
An Undecidable Problem in Correspondence Theory.L. A. Chagrova - 1991 - Journal of Symbolic Logic 56 (4):1261-1272.

View all 6 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles
Modal Sequents and Definability.Bruce M. Kapron - 1987 - Journal of Symbolic Logic 52 (3):756-762.
Elementary Definability and Completeness in General and Positive Modal Logic.Ernst Zimmermann - 2003 - Journal of Logic, Language and Information 12 (1):99-117.
Modal Logic Over Finite Structures.Eric Rosen - 1997 - Journal of Logic, Language and Information 6 (4):427-439.
Cylindric Modal Logic.Yde Venema - 1995 - Journal of Symbolic Logic 60 (2):591-623.

Monthly downloads

Added to index

2009-01-28

Total downloads

25 ( #198,618 of 2,152,250 )

Recent downloads (6 months)

4 ( #185,125 of 2,152,250 )

How can I increase my downloads?

My notes
Sign in to use this feature


Discussion
Order:
There  are no threads in this forum
Nothing in this forum yet.

Other forums