A note on strictly positive logics and word rewriting systems

DOI10.1007/978-3-319-69917-2_4zbMATH Open1429.03077arXiv1509.00666OpenAlexW2206760849MaRDI QIDQ5214732FDOQ5214732

Authors: Lev D. Beklemishev 

Publication date: 5 February 2020

Published in: Larisa Maksimova on Implication, Interpolation, and Definability (Search for Journal in Brave)

Abstract: We establish a natural translation from word rewriting systems to strictly positive polymodal logics. Thereby, the latter can be considered as a generalization of the former. As a corollary we obtain examples of undecidable strictly positive normal modal logics. The translation has its counterpart on the level of proofs: we formulate a natural deep inference proof system for strictly positive logics generalizing derivations in word rewriting systems. We also formulate some open questions related to the theory of modal companions of superintuitionistic logics that was initiated by L.L. Maximova and V.V. Rybakov.

Full work available at URL: https://arxiv.org/abs/1509.00666

Recommendations

• Rewrite rule systems for modal propositional logic
• On strictly positive modal logics with \textsf{S}4.3 frames
• Positive modal logic
• Axiomatization and polynomial solvability of strictly positive fragments of certain modal logics
• Pure strict implication logics

zbMATH Keywords

deep inferencesemi-Thue systemsstrictly positive logics

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Grammars and rewriting systems (68Q42)

Cites Work

• Modal companions of intermediate propositional logics
• On the positive fragment of the polymodal provability logic GLP
• Positive provability logic for uniform reflection principles
• Calibrating provability logic: from modal logic to reflection calculus
• A lattice of normal modal logics
• Islands of tractability for relational constraints: towards dichotomy results for the description logic \({\mathcal{EL}}\)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (8)

• AN ESCAPE FROM VARDANYAN’S THEOREM
• Reflection calculus and conservativity spectra
• VARIETIES OF POSITIVE MODAL ALGEBRAS AND STRUCTURAL COMPLETENESS
• Reflection algebras and conservation results for theories of iterated truth
• Positive First-order Logic on Words and Graphs
• Kripke completeness of strictly positive modal logics over meet-semilattices with operators
• Axiomatization and polynomial solvability of strictly positive fragments of certain modal logics
• Modal companions of \(K4^+\)

This page was built for publication: A note on strictly positive logics and word rewriting systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5214732)