×

A note on strictly positive logics and word rewriting systems. (English) Zbl 1429.03077

Odintsov, Sergei (ed.), Larisa Maksimova on implication, interpolation, and definability. Cham: Springer. Outst. Contrib. Log. 15, 61-70 (2018).
Summary: 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 finitely axiomatizable 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 make some observations and formulate open questions related to the theory of modal companions of superintuitionistic logics that was initiated by L. L. Maksimova and V. V. Rybakov [Algebra Logic 13, 105–122 (1975; Zbl 0315.02027); translation from Algebra Logika 13, 188–216 (1974)].
For the entire collection see [Zbl 1403.03008].

MSC:

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

Citations:

Zbl 0315.02027
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Baader, F. (2003). Resricted role-value-maps in a description logic with existential restrictions and terminological cycles. In D. Calvanese, G. De Giacomo, E. Franconi (Ed.), Proceeding of the 2003 International Workshop on Description Logics (DL 2003), Rome, Italy, September 5-7, 2003, Vol. 81, CEUR Workshop Proceedings, CEUR-WS.org.
[2] Beklemishev, L. D. (2012). Calibrating provability logic: from modal logic to reflection calculus. In T. Bolander, T. Braüner, S. Ghilardi, & L. Moss (Eds.), Advances in Modal Logic (Vol. 9, pp. 89-94). London: College Publications. · Zbl 1331.03040
[3] Beklemishev, L. D. (2014). Positive provability logic for uniform reflection principles. Annals of Pure and Applied Logic, 165(1), 82-105. · Zbl 1322.03041 · doi:10.1016/j.apal.2013.07.006
[4] Blok, W.J. (1976). Varieties of interior algebras, PhD thesis, University of Amsterdam.
[5] Chagrov, A.V. & Shehtman, V.B. (1995). Algorithmic aspects of propositional tense logics, In Lecture Notes in Computer Science (Vol. 933, pp. 442-455). · Zbl 1044.03513
[6] Chagrov, A. V., & Zakharyaschev, M. (1992). Modal companions of intermediate propositional logics. Studia Logica, 51(1), 49-82. · Zbl 0766.03015 · doi:10.1007/BF00370331
[7] Dashkov, E. V. (2012). O positivnom fragmente polimodalnoy logiki dokazuemosti GLP, Matematicheskie Zametki 91(3): 331-346. [Translation: “On the positive fragment of the polymodal provability logic GLP”. Mathematical Notes, 91(3), 318-333. · Zbl 1315.03113
[8] Davis, M., Sigal, R., & Weyuker, E.J. (1994). Computability, complexity, and languages: fundamentals of theoretical computer science (2nd ed.). Academic Press.
[9] Esakia, L. L. (1976). On modal companions of superintuitionistic logics. In VII Soviet Symposium on Logic. Kiev.
[10] Kikot, S., Kurucz, A., Tanaka, Y., Wolter, F. & Zakharyaschev, M. (2016). On the completeness of EL-equiations: First results. In 11th International Conference on Advances in Modal Logic, Short Papers (Budapest, 30 August - 2 September, 2016), pp. 82-87.
[11] Kurucz, A., Wolter, F. & Zakharyaschev, M. (2010). Islands of tractability for relational constraints: towards dichotomy results for the description logic EL. In Advances in Modal Logic Vol. 8 pp. 271-291. College Publications, London. · Zbl 1252.68275
[12] Kurucz, A., Tanaka, Y., Wolter, F., & Zakharyaschev, M. (2011). Conservativity of Boolean algebras with operators over semilattices with operators. Proceedings of TACL, 49-52.
[13] Maksimova, L.L. & Rybakov, V.V. (1974). A lattice of normal modal logics. Algebra i Logika, 13(2): 188-216. · Zbl 0315.02027
[14] Shehtman, V.B. (1982). Undecidable propositional calculi. InProblems of cybernetics. Non-classical logics and their applications, Moscow, pp. 74-116. In Russian. · Zbl 0499.03003
[15] Svyatlovsky, M. (2014) Positivnye fragmenty modalnykh logik, Manuscript, [Positive fragments of modal logics]. http://www.mi.ras.ru/ bekl/Papers/work_2.pdf.
[16] Wolter, F.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.