Sebastian Enqvist ; Yde Venema - Disjunctive bases: normal forms and model theory for modal logics

lmcs:4038 - Logical Methods in Computer Science, August 23, 2022, Volume 15, Issue 1 - https://doi.org/10.23638/LMCS-15(1:30)2019
Disjunctive bases: normal forms and model theory for modal logicsArticle

Authors: Sebastian Enqvist ; Yde Venema

    We present the concept of a disjunctive basis as a generic framework for normal forms in modal logic based on coalgebra. Disjunctive bases were defined in previous work on completeness for modal fixpoint logics, where they played a central role in the proof of a generic completeness theorem for coalgebraic mu-calculi. Believing the concept has a much wider significance, here we investigate it more thoroughly in its own right. We show that the presence of a disjunctive basis at the "one-step" level entails a number of good properties for a coalgebraic mu-calculus, in particular, a simulation theorem showing that every alternating automaton can be transformed into an equivalent nondeterministic one. Based on this, we prove a Lyndon theorem for the full fixpoint logic, its fixpoint-free fragment and its one-step fragment, and a Uniform Interpolation result, for both the full mu-calculus and its fixpoint-free fragment. We also raise the questions, when a disjunctive basis exists, and how disjunctive bases are related to Moss' coalgebraic "nabla" modalities. Nabla formulas provide disjunctive bases for many coalgebraic modal logics, but there are cases where disjunctive bases give useful normal forms even when nabla formulas fail to do so, our prime example being graded modal logic. We also show that disjunctive bases are preserved by forming sums, products and compositions of coalgebraic modal logics, providing tools for modular construction of modal logics admitting disjunctive bases. Finally, we consider the problem of giving a category-theoretic formulation of disjunctive bases, and provide a partial solution. Comment: This is a corrected version of the paper arXiv:1710.10706 published originally on 26/3, 2019


    Volume: Volume 15, Issue 1
    Published on: August 23, 2022
    Accepted on: February 19, 2019
    Submitted on: November 1, 2017
    Keywords: Computer Science - Logic in Computer Science

    1 Document citing this article

    Consultation statistics

    This page has been seen 1507 times.
    This article's PDF has been downloaded 386 times.