Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
DISJUNCTIVE BASES: NORMAL FORMS AND MODEL THEORY FOR MODAL LOGICS
Stockholm University, Faculty of Humanities, Department of Philosophy.
Number of Authors: 22019 (English)In: Logical Methods in Computer Science, ISSN 1860-5974, E-ISSN 1860-5974, Vol. 15, no 1, article id 30Article in journal (Refereed) Published
Abstract [en]

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, a Uniform Interpolation result, for both the full mu-calculus and its fixpoint-free fragment, and a Janin-Walukiewicz-style characterization theorem for the mu-calculus under slightly stronger assumptions. We also raise the questions, when a disjunctive basis exists, and how disjunctive bases arc 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.

Place, publisher, year, edition, pages
2019. Vol. 15, no 1, article id 30
Keywords [en]
Modal logic, fixpoint logic, automata, coalgebra, graded modal logic, Lyndon theorem, uniform interpolation, expressive completeness
National Category
Computer and Information Sciences Philosophy
Identifiers
URN: urn:nbn:se:su:diva-168465DOI: 10.23638/LMCS-15(1:30)2019ISI: 000463358400017OAI: oai:DiVA.org:su-168465DiVA, id: diva2:1313173
Available from: 2019-05-02 Created: 2019-05-02 Last updated: 2019-05-02Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Search in DiVA

By author/editor
Enqvist, Sebastian
By organisation
Department of Philosophy
In the same journal
Logical Methods in Computer Science
Computer and Information SciencesPhilosophy

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 33 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf