Answers are grounded in this paper and cite their sources.
We study the existence of finite characterisations for modal formulas. A finite characterisation of a modal formula φ is a finite collection of positive and negative examples that distinguishes φ from every other, non-equivalent modal formula, where an example is a finite pointed Kripke structure. This definition can be restricted to specific frame classes and to fragments of the modal language: a modal fragment ℒ admits finite characterisations with respect to a frame class ℱ if every formula φ ∈ ℒ has a finite characterisation with respect to ℒ consisting of examples that are based on frames in ℱ. Finite characterisations are useful for illustration, interactive specification and debugging of formal specifications, and their existence is a precondition for exact learnability with membership queries. We show that the full modal language admits finite characterisations with respect to a frame class ℱ only when the modal logic of ℱ is locally tabular. We then study which modal fragments, freely generated by some set of connectives, admit finite characterisations. Our main result is that the positive modal language without the truth-constants ⊤ and ⊥ admits finite characterisations w.r.t. the class of all frames. This result is essentially optimal: finite characterisability fails when the language is extended with the truth constant ⊤ or ⊥ or with all but very limited forms of negation.
No takes yet. Share an insight, caveat, or question.
Cate et al. (2024) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: