Algorithmic problems concerning first-order definability of modal formulas on the class of all finite frames (Q1908859)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Algorithmic problems concerning first-order definability of modal formulas on the class of all finite frames |
scientific article; zbMATH DE number 851969
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Algorithmic problems concerning first-order definability of modal formulas on the class of all finite frames |
scientific article; zbMATH DE number 851969 |
Statements
Algorithmic problems concerning first-order definability of modal formulas on the class of all finite frames (English)
0 references
27 August 1996
0 references
It is proved that no algorithm is capable of deciding whether an arbitrary given modal formula is (globally or locally) first-order definable on the class of finite frames. It is also shown that the (local as well as global) semantical consequence relation on finite frames is undecidable too.
0 references
first-order definability
0 references
undecidability
0 references
finite frames
0 references
semantical consequence
0 references
0 references
