Learning Modal Formulas via Dualities
Raoul Koudijs
Abstract:
We initiate the study of finite characterisations and exact learnability of modal languages. A finite characterisation of a modal formula w.r.t. a class of formulas is a finite set of finite models (labelled either positive or negative) which distinguishes this formula from every other formula from that class. A language is finitely characterisable if every formula in it has a finite characterisation w.r.t. it. We show that normal modal logics are finitely characterisable if and only if they are locally tabular. Further, we define the category of pointed Kripke models and weak simulations and show that the existence of dualities in this category relate to finite characterisability of the positive modal language without the truth-constants ⊤ and ⊥. In fact, we show that our techniques apply to a larger class of uniform formulas. Moreover, our results are essentially optimal as we show that allowing any kind of non-uniformity makes the language non-characterisable. Throughout, we indicate what exact learning algorithms can be obtained from these characterisations.