A note on strictly positive logics and word rewriting systems

DOI10.1007/978-3-319-69917-2_4MaRDI QIDQ5214732zbMATH OpenOpenAlexFDO

Authors Lev D. Beklemishev

Publication date 5 February 2020

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3786733 (Why is no real title available?)
• scientific article; zbMATH DE number 2079045 (Why is no real title available?)
• A lattice of normal modal logics
• Calibrating provability logic: from modal logic to reflection calculus
• Islands of tractability for relational constraints: towards dichotomy results for the description logic \({\mathcal{EL}}\)
• Modal companions of intermediate propositional logics
• On the positive fragment of the polymodal provability logic GLP
• Positive provability logic for uniform reflection principles

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)