{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T09:58:22Z","timestamp":1763978302683,"version":"3.37.3"},"reference-count":33,"publisher":"Oxford University Press (OUP)","issue":"8","license":[{"start":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T00:00:00Z","timestamp":1667865600000},"content-version":"vor","delay-in-days":1,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"FCT\/MCTES"},{"DOI":"10.13039\/100006129","name":"FCT","doi-asserted-by":"publisher","award":["PD\/BD\/135513\/2018"],"award-info":[{"award-number":["PD\/BD\/135513\/2018"]}],"id":[{"id":"10.13039\/100006129","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,12,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Recent compositionality results in logic have highlighted the advantages of enlarging the traditional notion of logical matrix semantics, namely by incorporating non-determinism and partiality. Still, several important properties which are known to be computable for finite logical matrices have not been studied in the wider context of partial non-deterministic matrices (PNmatrices). In this paper, we study how incorporating non-determinism and\/or partiality in logical matrices impacts on the computational properties of some natural problems regarding their induced logics and concretely their sets of theorems. We show that, while for some of these problems there is no relevant computational impact, there are problems whose computational complexity increases and still other problems that simply become undecidable. In particular, we show that the problem of checking whether the logics characterized by two finite PNmatrices have the same set of theorems is not decidable. This undecidability result explores the connection between PNmatrices and term-DAG-automata, where the universality problem is known to be undecidable. This link also motivates a final contribution, in the form of a pumping-like lemma, which can be used, in some cases, to show that a given logic cannot be characterized by a finite PNmatrix.<\/jats:p>","DOI":"10.1093\/logcom\/exac073","type":"journal-article","created":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T06:44:39Z","timestamp":1667889879000},"page":"1694-1719","source":"Crossref","is-referenced-by-count":2,"title":["Computational properties of finite PNmatrices"],"prefix":"10.1093","volume":"32","author":[{"given":"Pedro","family":"Filipe","sequence":"first","affiliation":[{"name":"SQIG - Instituto de Telecomunica\u00e7\u00f5es Dep. Matem\u00e1tica , Instituto Superior T\u00e9cnico Universidade de Lisboa, 1049-001 Lisboa, Portugal"}]},{"given":"S\u00e9rgio","family":"Marcelino","sequence":"additional","affiliation":[{"name":"SQIG - Instituto de Telecomunica\u00e7\u00f5es Dep. Matem\u00e1tica , Instituto Superior T\u00e9cnico Universidade de Lisboa, 1049-001 Lisboa, Portugal"}]},{"given":"Carlos","family":"Caleiro","sequence":"additional","affiliation":[{"name":"SQIG - Instituto de Telecomunica\u00e7\u00f5es Dep. Matem\u00e1tica , Instituto Superior T\u00e9cnico Universidade de Lisboa, 1049-001 Lisboa, Portugal"}]}],"member":"286","published-online":{"date-parts":[[2022,11,7]]},"reference":[{"key":"2023110914573001700_ref1","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/j.ipl.2005.02.004","article-title":"Closure properties and decision problems of dag automata","volume":"94","author":"Anantharaman","year":"2005","journal-title":"Information Processing Letters"},{"key":"2023110914573001700_ref2","article-title":"Non-deterministic semantics for families of paraconsistent logics","volume-title":"Handbook of Paraconsistency","author":"Avron","year":"2007"},{"key":"2023110914573001700_ref3","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1093\/logcom\/exs039","article-title":"Cut-free sequent calculi for C-systems with generalized finite-valued semantics","volume":"23","author":"Avron","year":"2013","journal-title":"Journal of Logic and Computation"},{"key":"2023110914573001700_ref4","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1093\/logcom\/exi001","article-title":"Non-deterministic multiple-valued structures","volume":"15","author":"Avron","year":"2005","journal-title":"Journal of Logic and Computation"},{"key":"2023110914573001700_ref5","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/978-94-007-0479-4_4","article-title":"Non-deterministic semantics for logical systems","volume-title":"Handbook of Philosophical Logic","author":"Avron","year":"2011"},{"key":"2023110914573001700_ref6","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1017\/S1755020318000321","article-title":"Rexpansions of non-deterministic matrices and their applications in nonclassical logics","volume":"12","author":"Avron","year":"2019","journal-title":"The Review of Symbolic Logic"},{"volume-title":"Theory of Effective Propositional Paraconsistent Logics","year":"2018","author":"Avron","key":"2023110914573001700_ref7"},{"key":"2023110914573001700_ref8","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/s10817-013-9273-x","article-title":"Finite-valued semantics for canonical labelled calculi","volume":"51","author":"Baaz","year":"2013","journal-title":"Journal of Automated Reasoning"},{"key":"2023110914573001700_ref9","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/978-3-662-59533-6_6","article-title":"Analytic calculi for monadic PNmatrices","volume-title":"Logic, Language, Information, and Computation (WoLLIC 2019)","author":"Caleiro","year":"2019"},{"article-title":"Modular semantics for combined many-valued logics","year":"2021","author":"Caleiro","key":"2023110914573001700_ref10"},{"key":"2023110914573001700_ref11","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/978-3-030-71258-7_3","article-title":"On axioms and rexpansions","volume-title":"Arnon Avron on Semantics and Proof Theory of Non-Classical Logics","author":"Caleiro","year":"2021"},{"key":"2023110914573001700_ref12","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1109\/ISMVL49045.2020.000-1","article-title":"Infectious semantics and analytic calculi for even more inclusion logics","volume-title":"2020 IEEE 50th International Symposium on Multiple-Valued Logic","author":"Caleiro","year":"2020"},{"key":"2023110914573001700_ref13","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/j.fss.2017.10.014","article-title":"Characterizing finite-valuedness","volume":"345","author":"Caleiro","year":"2018","journal-title":"Fuzzy Sets and Systems"},{"key":"2023110914573001700_ref14","first-page":"1","article-title":"A taxonomy of C-systems","volume-title":"Paraconsistensy: The Logical Way to the Inconsistent","author":"Carnielli","year":"2002"},{"key":"2023110914573001700_ref15","article-title":"Automata on DAG representations of finite trees","volume-title":"Technical Report MPI-I-1999-2-001","author":"Charatonik","year":"1999"},{"key":"2023110914573001700_ref16","first-page":"5:1","article-title":"Taming paraconsistent (and other) logics: An algorithmic approach","volume":"16","author":"Ciabattoni","year":"2014","journal-title":"ACM Transactions on Computational Logic"},{"article-title":"Tree automata techniques and applications","year":"2008","author":"Comon","key":"2023110914573001700_ref17"},{"key":"2023110914573001700_ref18","first-page":"151","article-title":"The complexity of theorem-proving procedures","volume-title":"Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC \u201871","author":"Cook","year":"1971"},{"volume-title":"Abstract Algebraic Logic","year":"2016","author":"Font","key":"2023110914573001700_ref19"},{"key":"2023110914573001700_ref20","doi-asserted-by":"crossref","first-page":"156","DOI":"10.3390\/e22020156","article-title":"Non-deterministic semantics for quantum states","volume":"22","author":"Jorge","year":"2020","journal-title":"Entropy"},{"key":"2023110914573001700_ref21","doi-asserted-by":"crossref","first-page":"182","DOI":"10.2307\/2266783","article-title":"A test for the existence of tautologies according to many-valued truth-tables","volume":"15","author":"Kalicki","year":"1950","journal-title":"The Journal of Symbolic Logic"},{"key":"2023110914573001700_ref22","doi-asserted-by":"crossref","first-page":"161","DOI":"10.2307\/2267687","article-title":"A test for the equality of truth-tables","volume":"17","author":"Kalicki","year":"1952","journal-title":"The Journal of Symbolic Logic"},{"key":"2023110914573001700_ref23","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","article-title":"Reducibility among combinatorial problems","volume-title":"Complexity of Computer Computations","author":"Karp","year":"1972"},{"volume-title":"Function Algebras on Finite Sets: A Basic Course on Many-Valued Logic and Clone Theory","year":"2006","author":"Lau","key":"2023110914573001700_ref24"},{"key":"2023110914573001700_ref25","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/s11787-021-00280-7","article-title":"An unexpected boolean connective","volume":"16","author":"Marcelino","year":"2021","journal-title":"Logica Universalis"},{"key":"2023110914573001700_ref26","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1007\/978-3-662-55386-2_17","article-title":"Disjoint fibring of non-deterministic matrices","volume-title":"Logic, Language, Information, and Computation (WoLLIC 2017)","author":"Marcelino","year":"2017"},{"key":"2023110914573001700_ref27","doi-asserted-by":"crossref","first-page":"5373","DOI":"10.1007\/s11229-019-02142-8","article-title":"Axiomatizing non-deterministic many-valued generalized consequence relations","volume":"198","author":"Marcelino","year":"2019","journal-title":"Synthese"},{"key":"2023110914573001700_ref28","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/978-3-030-93100-1_12","article-title":"Computational properties of partial non-deterministic matrices and their logics","volume-title":"Logical Foundations of Computer Science (LFCS2022)","author":"Marcelino","year":"2022"},{"key":"2023110914573001700_ref29","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/s11225-009-9196-z","article-title":"What is a non-truth-functional logic?","volume":"92","author":"Marcos","year":"2009","journal-title":"Studia Logica"},{"key":"2023110914573001700_ref30","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1109\/ISMVL51352.2021.00022","article-title":"Untruth, falsity and non-deterministic semantics","volume-title":"2021 IEEE 51st International Symposium on Multiple-Valued Logic","author":"Omori","year":"2021"},{"key":"2023110914573001700_ref31","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1090\/pspum\/025\/0363802","article-title":"Completeness and axiomatizability in many-valued logic","volume-title":"Proceedings of the Tarski Symposium","author":"Scott","year":"1974"},{"key":"2023110914573001700_ref32","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511565687","volume-title":"Multiple-Conclusion Logic","author":"Shoesmith","year":"1978"},{"volume-title":"Theory of Logical Calculi","year":"1998","author":"W\u00f3jcicki","key":"2023110914573001700_ref33"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/32\/8\/1694\/47846397\/exac073.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/32\/8\/1694\/47846397\/exac073.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,9]],"date-time":"2023-11-09T15:32:23Z","timestamp":1699543943000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/32\/8\/1694\/6795169"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,7]]},"references-count":33,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2022,11,7]]},"published-print":{"date-parts":[[2022,12,9]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exac073","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"type":"print","value":"0955-792X"},{"type":"electronic","value":"1465-363X"}],"subject":[],"published-other":{"date-parts":[[2022,12]]},"published":{"date-parts":[[2022,11,7]]}}}