[en] We study many-valued coalgebraic logics with semi-primal algebras of
truth-degrees. We provide a systematic way to lift endofunctors defined on the
variety of Boolean algebras to endofunctors on the variety generated by a
semi-primal algebra. We show that this can be extended to a technique to lift
classical coalgebraic logics to many-valued ones, and that (one-step)
completeness and expressivity are preserved under this lifting. For specific
classes of endofunctors, we also describe how to obtain an axiomatization of
the lifted many-valued logic directly from an axiomatization of the original
classical one. In particular, we apply all of these techniques to classical
modal logic.
Disciplines :
Sciences informatiques Mathématiques
Auteur, co-auteur :
Kurz, Alexander
POIGER, Wolfgang ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Mathematics (DMATH)
TEHEUX, Bruno ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Mathematics (DMATH)
Co-auteurs externes :
yes
Langue du document :
Anglais
Titre :
Many-valued coalgebraic logic over semi-primal varieties
Date de publication/diffusion :
17 juillet 2024
Titre du périodique :
Logical Methods in Computer Science
eISSN :
1860-5974
Maison d'édition :
Centre pour la Communication Scientifique Directe (CCSD)
[ARVL10] J. Adámek, J. Rosický, E. M. Vitale, and F. W. Lawvere. Algebraic Theories: A Categorical Introduction to General Algebra, volume 184 of Cambridge Tracts in Mathematics. Cambridge University Press, 2010.
[Baa96] M. Baaz. Infinite-valued Gödel logics with 0-1-projections and relativizations. In P. Hájek, editor, Proc. Gödel’96, Logic Foundations of Mathematics, Computer Science and Physics – Kurt Gödel’s Legacy, Lecture Notes in Logic 6, pages 23–33, Brno, 1996. Springer.
[BBDG22] G. Bezhanishvili, N. Bezhanishvili, and J. De Groot. A coalgebraic approach to dualities for neighborhood frames. Logical Methods in Computer Science, 18(3):4:1–4:39, 2022. doi:10.46298/lmcs-18(3:4)2022.
[BBKK18] P. Baldan, F. Bonchi, H. Kerstan, and B. König. Coalgebraic behavioral metrics. Logical Methods in Computer Science, 14(3):1–61, 2018. doi:10.23638/LMCS-14(3:20)2018.
[BD16] M. Bílková and M. Dostál. Expressivity of many-valued modal logics, coalgebraically. In J. Väänänen, Å. Hirvonen, and R. de Queiroz, editors, Logic, Language, Information, and Computation, pages 109–124. Springer Berlin Heidelberg, 2016. doi:10.1007/978-3-662-52921-8_8.
[BdRV01] P. Blackburn, M. de Rijke, and Y. Venema. Modal Logic, volume 53 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2001. doi:10.1017/CBO9781107050884.
[BEGR11] F. Bou, F. Esteva, L. Godo, and R. O. Rodríguez. On the minimum many-valued modal logic over a finite residuated lattice. Journal of Logic and Computation, 21(5):739–790, 2011. doi:10.1093/logcom/exp062.
[BFGR91] V. Boicescu, A. Filipoiu, G. Georgescu, and S. Rudeanu. Lukasiewicz-Moisil algebras, volume 49 of Annals of Discrete Mathematics. North-Holland, Amsterdam, 1991.
[BK05] M. M. Bonsangue and A. Kurz. Duality for logics of transition systems. In V. Sassone, editor, Foundations of Software Science and Computational Structures, pages 455–469. Springer Berlin Heidelberg, 2005. doi:10.1007/978-3-540-31982-5_29.
[BK06] M. M. Bonsangue and A. Kurz. Presenting functors by operations and equations. In L. Aceto and A. Ingólfsdóttir, editors, Foundations of Software Science and Computation Structures, pages 172–186. Springer Berlin Heidelberg, 2006. doi:10.1007/11690634_12.
[BKPV13] M. Bílková, A. Kurz, D. Petrişan, and J. Velebil. Relation lifting, with an application to the many-valued cover modality. Logical Methods in Computer Science, 9(4):739–790, 2013. doi:10.2168/LMCS-9(4:8)2013.
[BS81] S. Burris and H. P. Sankappanavar. A Course in Universal Algebra, volume 78 of Graduate Texts in Mathematics. Springer New York, 1981.
[Bur75] S. Burris. Boolean powers. Algebra Universalis, 5:341–360, 1975. doi:10.1007/BF02485268.
[Bur92] S. Burris. Discriminator varieties and symbolic computation. Journal of Symbolic Computation, 13:175–207, 1992. doi:10.1016/S0747-7171(08)80089-2.
[CD98] D. M. Clark and B. A. Davey. Natural Dualities for the Working Algebraist, volume 57 of Cambridge studies in advanced mathematics. Cambridge University Press, 1998.
[CDM00] R. L. O. Cignoli, I. M. L. D’Ottaviano, and D. Mundici. Algebraic Foundations of Many-Valued Reasoning, volume 7 of Trends in Logic. Springer Dordrecht, 2000. doi:10.1007/978-94-015-9480-6.
[Cig82] R. Cignoli. Proper n-valued ̷lukasiewicz algebras as s-algebras of ̷lukasiewicz n-valued propositional calculi. Studia Logica, 41(1):3–16, 1982. doi:10.1007/BF00373490.
[CP04] C. Cîrstea and D. Pattinson. Modular construction of modal logics. In P. Gardner and N. Yoshida, editors, CONCUR 2004-Concurrency Theory, pages 258–275. Springer Berlin Heidelberg, 2004. doi:10.1007/978-3-540-28644-8_17.
[CR10] X. Caicedo and R. Rodriguez. Standard Gödel modal logics. Studia Logica, 94:189–214, 2010. doi:10.1007/s11225-010-9230-1.
[DG07] D. Diaconescu and G. Georgescu. Tense operators on MV-algebras and ̷Lukasiewicz-Moisil algebras. Fundamenta Informaticae, 81(4):379–408, 2007.
[Dos89] K. Dosen. Duality between modal algebras and neighbourhood frames. Studia Logica, 48(2):219– 234, 1989. doi:10.1007/BF02770513.
[DSW91] B. A. Davey, V. Schumann, and H. Werner. From the subalgebras of the square to the discriminator. Algebra Universalis, 28:500–519, 1991. doi:10.1007/BF01195860.
[Fit91] M. C. Fitting. Many-valued modal logics. Fundamenta Informaticae, 15(3-4):235–254, 1991. doi:10.3233/FI-1991-153-404.
[Fos53] A. L. Foster. Generalized ”Boolean” theory of universal algebras. Part I. Mathematische Zeitschrift, 58:306–336, 1953. doi:10.1007/BF01174150.
[Fos67] A. L. Foster. Semi-primal algebras; Characterization and normal-decomposition. Mathematische Zeitschrift, 99:105–116, 1967. doi:10.1007/BF01123742.
[Fos54] A. L. Foster. Generalized ”Boolean” theory of universal algebras. Part II. Identities and subdirect sums of functionally complete algebras. Mathematische Zeitschrift, 59:191–199, 1953/54. doi: 10.1007/BF01180250.
[FP64a] A. L. Foster and A. F. Pixley. Semi-categorical algebras. I. Semi-primal algebras. Mathematische Zeitschrift, 83:147–169, 1964. doi:10.1007/BF01111252.
[FP64b] A. L. Foster and A. F. Pixley. Semi-categorical algebras. II. Mathematische Zeitschrift, 85:169–184, 1964. doi:10.1007/BF01110374.
[HKP09] H. H. Hansen, C. Kupke, and E. Pacuit. Neighbourhood structures: Bisimilarity and basic model theory. Logical Methods in Computer Science, 5(2):1–38, 2009. doi:10.2168/LMCS-5(2:2)2009.
[HT13] G. Hansoul and B. Teheux. Extending ̷Lukasiewicz logics with a modality: Algebraic approach to relational semantics. Studia Logica, 101:505–545, 2013. doi:10.1007/s11225-012-9396-9.
[Hu69] T.-K. Hu. Stone duality for primal algebra theory. Mathematische Zeitschrift, 110:180–198, 1969. doi:10.1007/BF01110209.
[Hu71] T.-K. Hu. On the topological duality for primal algebra theory. Algebra Universalis, 1:152–154, 1971. doi:10.1007/BF02944971.
[Joh82] P. T. Johnstone. Stone spaces, volume 3 of Cambridge studies in advanced mathematics. Cambridge University Press, 1982.
[JS09] B. Jacobs and A. Sokolova. Exemplaric expressivity of modal logics. Journal of Logic and Computation, 20(5):1041–1068, 2009. doi:10.1093/logcom/exn093.
[KKP04] C. Kupke, A. Kurz, and D. Pattinson. Algebraic semantics for coalgebraic logics. Electronic Notes in Theoretical Computer Science, 106:219–241, 2004. doi:10.1016/j.entcs.2004.02.037.
[KKV03] C. Kupke, A. Kurz, and Y. Venema. Stone coalgebras. Theoretical Computer Science, 327(1):109– 134, 2003. doi:10.1016/S1571-0661(04)80638-8.
[Kli07] B. Klin. Coalgebraic modal logic beyond sets. Electronic Notes in Theoretical Computer Science, 173:177–201, 2007. Proceedings of the 23rd Conference on the Mathematical Foundations of Programming Semantics (MFPS XXIII). doi:10.1016/j.entcs.2007.02.034.
[Kow04] T. Kowalski. Semisimplicity, edpc and discriminator varieties of residuated lattices. Studia Logica, 77:255–265, 2004. doi:10.1023/B:STUD.0000037129.58589.0c.
[KP10] A. Kurz and D. Petrişan. Presenting functors on many-sorted varieties and applications. Information and Computation, 208(12):1421–1446, 2010. doi:10.1016/j.ic.2009.11.007.
[KP11] C. Kupke and D. Pattinson. Coalgebraic semantics of modal logics: An overview. Theoretical Computer Science, 412(38):5070–5094, 2011. doi:10.1016/j.tcs.2011.04.023.
[KP23] A. Kurz and W. Poiger. Many-Valued Coalgebraic Logic: From Boolean Algebras to Primal Varieties. In P. Baldan and V. de Paiva, editors, 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023), volume 270 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1–17:17, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.CALCO.2023.17.
[KPT24] A. Kurz, W. Poiger, and B. Teheux. New perspectives on semi-primal varieties. Journal of Pure and Applied Algebra, 228(4):107525, 2024. doi:10.1016/j.jpaa.2023.107525.
[KR12] A. Kurz and J. Rosický. Strongly complete logics for coalgebras. Logical Methods in Computer Science, 8(3):1–32, 2012. doi:10.2168/LMCS-8(3:14)2012.
[KT17] T. Kroupa and B. Teheux. Modal extensions of ̷Lukasiewicz logic for modelling coalitional power. Journal of Logic and Computation, 27(1):129–154, 2017. doi:10.1093/logcom/exv081.
[KW74] K. Keimel and H. Werner. Stone duality for varieties generated by quasi-primal algebras. Memoirs of the American Mathematical Society, 148:59–85, 1974.
[LL23] C.-Y. Lin and C.-J. Liau. Many-valued coalgebraic modal logic: One-step completeness and finite model property. Fuzzy Sets and Systems, 467:108564, 2023. doi:10.1016/j.fss.2023.108564.
[Mar09] Y. Maruyama. Algebraic study of lattice-valued logic and lattice-valued modal logic. In R. Ramanujam and S. Sarukkai, editors, Logic and Its Applications. ICLA, pages 170–184. Springer Berlin Heidelberg, 2009. doi:10.1007/978-3-540-92701-3_12.
[Mar12] Y. Maruyama. Natural duality, modality, and coalgebra. Journal of Pure and Applied Algebra, 216(3):565–580, 2012. doi:10.1016/j.jpaa.2011.07.002.
[ML97] S. Mac Lane. Categories for the Working Mathematician, volume 5 of Graduate Texts in Mathematics. Springer New York, second edition, 1997. doi:10.1007/978-1-4757-4721-8.
[MM18] M. Marti and G. Metcalfe. Expressivity in chain-based modal logics. Archive for Mathematical Logic, 57:361–380, 2018. doi:10.1007/s00153-017-0573-4.
[Mos99] L. S. Moss. Coalgebraic logic. Annals of Pure and Applied Logic, 96(1):277–317, 1999. doi: 10.1016/S0168-0072(98)00042-6.
[Nie01] P. Niederkorn. Natural dualities for varieties of MV-algebras, I. Journal of Mathematical Analysis and Applications, 255(1):58–73, 2001. doi:10.1006/jmaa.2000.7153.
[Pac17] E. Pacuit. Neighborhood Semantics for Modal Logic. Short Textbooks in Logic. Springer Cham, 2017. doi:10.1007/978-3-319-67149-9.
[Pal04] A. Palmigiano. A coalgebraic view on positive modal logic. Theoretical Computer Science, 327(1):175–195, 2004. Selected Papers of CMCS ’03. doi:10.1016/j.tcs.2004.07.026.
[Pat03] D. Pattinson. Coalgebraic modal logic: Soundness, completeness and decidability of local consequence. Theoretical Computer Science, 309(1):177–193, 2003. doi:10.1016/S0304-3975(03) 00201-9.
[Pat04] D. Pattinson. Expressive logics for coalgebras via terminal sequence induction. Notre Dame Journal of Formal Logic, 45(1):19–33, 2004. doi:10.1305/ndjfl/1094155277.
[Pix71] A. F. Pixley. The ternary discriminator function in universal algebra. Mathematische Annalen, 191:167–180, 1971. doi:10.1007/BF01578706.
[Pri08] G. Priest. Many-valued modal logics: A simple approach. The Review of Symbolic Logic, 1(2):190–203, 2008. doi:10.1017/S1755020308080179.
[Qua79] R. W. Quackenbush. Primality: The influence of Boolean algebras in universal algebra. (Appendix 5). In Grätzer, G. Universal Algebra. Second Edition, pages 401–416. Springer New York, 1979.
[RJJ17] U. Rivieccio, A. Jung, and R. Jansana. Four-valued modal logic: Kripke semantics and duality. Journal of Logic and Computation, 27(1):155–199, 2017. doi:10.1093/logcom/exv038.
[Rut00] J. J. M. M. Rutten. Universal coalgebra: A theory of systems. Theoretical Computer Science, 249(1):3–80, 2000. doi:10.1016/S0304-3975(00)00056-6.
[Sch08] L. Schröder. Expressivity of coalgebraic modal logic: The limits and beyond. Theoretical Computer Science, 390(2):230–247, 2008. doi:10.1016/j.tcs.2007.09.023.
[SKAR18] A. Schiendorfer, A. Knapp, G. Anders, and W. Reif. MiniBrass: Soft constraints for MiniZinc. Constraints, 23(4):403–450, 2018. doi:10.1007/s10601-018-9289-2.
[Teh14] B. Teheux. Propositional dynamic logic for searching games with errors. Journal of Applied Logic, 12(4):377–394, 2014. doi:10.1016/j.jal.2014.04.001.
[Trn69] V. Trnková. Some properties of set functors. Commentationes Mathematicae Universitatis Carolinae, 10(2):323–352, 1969.
[VEG17] A. Vidal, F. Esteva, and L. Godo. On modal extensions of product fuzzy logic. Journal of Logic and Computation, 27(1):299–336, 2017. doi:10.1093/logcom/exv046.
[VEG20] A. Vidal, F. Esteva, and L. Godo. Axiomatizing logics of fuzzy preferences using graded modalities. Fuzzy Sets and Systems, 401:163–188, 2020. doi:10.1016/j.fss.2020.01.002.
