LisMath Seminar 

21/04/2022, 11:00 — 11:30 — Online
Pedro Filipe, Instituto Superior Técnico, Universidade de Lisboa

Partial non-deterministic matrices and their computational properties

Logical matrices are arguably the most common algebraic semantical structures used for propositional logics. After Lukasiewicz, a logical matrix consists of an underlying algebra, functionally interpreting logical connectives over a set of truth-values, together with a subset of designated truth-values. In 2005, Avron and Lev [1] introduced non-deterministic matrices (Nmatrices), a generalization of logical matrices where the connectives are interpreted, not as functions, but as multi-functions.

This notion was further generalized by Baaz et al. [2] by also allowing for partiality (PNmatrices). Since their introduction, these generalized structures have been gaining traction amongst logicians, as the added expressiveness allows for finite characterizations of a much wider class of logics and general recipes for various problems in logic, such as procedures to constructively update semantics when imposing new axioms [4,5], or effectively combining semantics for two logics, capturing the effect of joining their axiomatizations [3,6,7].

However, several problems whose computational and complexity status is well studied for traditional matrices, have not yet been studied in the wider context of PNmatrices. In this talk, we review the basic notions of algebraic semantics, introduce partial non-deterministic matrices and present our recent results regarding the computational and complexity status of some of these problems.

References:

[1] A. Avron and I. Lev. Non-deterministic multiple-valued structures. Journal of Logic and Computation, 15(3):241–261, 2005.

[2] M. Baaz, O. Lahav, and A. Zamansky. Finite-valued semantics for canonical labelled calculi. Journal of Automated Reasoning, 51(4):401– 430, 2013.

[3] C. Caleiro and S. Marcelino. Modular semantics for combined many- valued logics, 2021. Submitted.

[4] C. Caleiro and S. Marcelino. On axioms and rexpansions. In O. Arieli and A. Zamansky, editors, Arnon Avron on Semantics and Proof The- ory of Non-Classical Logics, volume 21 of Outstanding Contributions to Logic. Springer, Cham, 2021. doi:https://doi.org/10.1007/ 978-3-030-71258-7_3.

[5] A. Ciabattoni, O. Lahav, L. Spendier, and A. Zamansky. Taming para- consistent (and other) logics: An algorithmic approach. ACM Transactions on Computational Logic, 16(1):5:1–5:16, 2014.

[6] S. Marcelino. An unexpected boolean connective. Logica Universalis, 2021. doi:10.1007/s11787-021-00280-7.

[7] S. Marcelino and C. Caleiro. Disjoint fibring of non-deterministic ma- trices. In J. Kennedy and R. de Queiroz, editors, Logic, Language, In- formation, and Computation (WoLLIC 2017), volume 10388 of LNCS, pages 242–255. Springer-Verlag, 2017.