{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T16:25:03Z","timestamp":1781281503678,"version":"3.54.1"},"reference-count":24,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2023,10,13]],"date-time":"2023-10-13T00:00:00Z","timestamp":1697155200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,6,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>In this work, we present polyhedral semantics as a means to tractably approximate \u0141ukasiewicz infinitely-valued logic (\u0141\u221e). As \u0141\u221e is an expressive multivalued propositional logic whose decision problem is NP-complete, we show how to to obtain an approximation for this problem providing a family of multivalued logics over the same language as \u0141\u221e. Each element of the family is associated to a polynomial-time linear program, thus providing a tractable way of deciding each intermediate step. We also investigate properties of the logic system derived from polyhedral semantics and the details of an algorithm for the approximation process.<\/jats:p>","DOI":"10.1093\/logcom\/exad059","type":"journal-article","created":{"date-parts":[[2023,10,13]],"date-time":"2023-10-13T15:12:45Z","timestamp":1697209965000},"source":"Crossref","is-referenced-by-count":2,"title":["Polyhedral semantics and the tractable approximation of \u0141ukasiewicz infinitely-valued logic"],"prefix":"10.1093","volume":"35","author":[{"given":"Marcelo","family":"Finger","sequence":"first","affiliation":[{"name":"Institute of Mathematics and Statistics , University of S\u00e3o Paulo, S\u00e3o Paulo, 05508-090,","place":["Brazil"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sandro","family":"Preto","sequence":"additional","affiliation":[{"name":"Institute of Mathematics and Statistics , University of S\u00e3o Paulo, S\u00e3o Paulo, 05508-090,","place":["Brazil"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2023,10,13]]},"reference":[{"key":"2025061108221029800_ref1","first-page":"364","article-title":"Pushing the el envelope","volume-title":"Proceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI\u201905","author":"Baader","year":"2005"},{"key":"2025061108221029800_ref2","first-page":"3","volume-title":"Description Logics","author":"Baader","year":"2004"},{"key":"2025061108221029800_ref3","doi-asserted-by":"crossref","first-page":"2187","DOI":"10.1007\/s00500-018-3365-9","article-title":"New complexity results for \u0141ukasiewicz logic","volume":"23","author":"Bofill","year":"2019","journal-title":"Soft Computing"},{"key":"2025061108221029800_ref4","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1090\/S0002-9947-1958-0094302-9","article-title":"Algebraic analysis of many valued logics","volume":"88","author":"Chang","year":"1958","journal-title":"Transactions of the American Mathematical Society"},{"key":"2025061108221029800_ref5","article-title":"Algebraic foundations of many-valued reasoning","volume-title":"Trends in Logic","author":"Cignoli","year":"2000"},{"key":"2025061108221029800_ref6","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/j.tcs.2013.02.014","article-title":"Semantics and proof-theory of depth bounded Boolean logics","volume":"480","author":"D\u2019Agostino","year":"2013","journal-title":"Theoretical Computer Science"},{"key":"2025061108221029800_ref7","article-title":"Tractable depth-bounded approximations to fde and its satellites","author":"D\u2019Agostino","year":"2023"},{"key":"2025061108221029800_ref8","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","article-title":"Linear-time algorithms for testing the satisfiability of propositional horn formulae","volume":"1","author":"Dowling","year":"1984","journal-title":"The Journal of Logic Programming"},{"key":"2025061108221029800_ref9","first-page":"71","article-title":"Tableaux for approximate reasoning","volume-title":"IJCAI-2001 Workshop on Inconsistency in Data and Knowledge","author":"Finger"},{"key":"2025061108221029800_ref10","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.tcs.2006.01.007","article-title":"The universe of propositional approximations","volume":"355","author":"Finger","year":"2006","journal-title":"Theoretical Computer Science"},{"key":"2025061108221029800_ref11","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1093\/logcom\/exl018","article-title":"Anytime approximations of classical logic from above","volume":"17","author":"Finger","year":"2007","journal-title":"Journal of Logic and Computation"},{"key":"2025061108221029800_ref12","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/S0927-0507(89)01003-0","article-title":"Chapter II linear programming","volume-title":"Optimization","author":"Goldfarb","year":"1989"},{"key":"2025061108221029800_ref13","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/BF01530787","article-title":"Many-valued logic and mixed integer programming","volume":"12","author":"H\u00e4hnle","year":"1994","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"2025061108221029800_ref14","article-title":"Metamathematics of fuzzy logic","volume-title":"Trends in Logic","author":"H\u00e1jek","year":"1998"},{"key":"2025061108221029800_ref15","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1002\/malq.19670130104","article-title":"The decision problem for a class of first-order formulas in which all disjunctions are binary","volume":"13","author":"Krom","year":"1967","journal-title":"Mathematical Logic Quarterly"},{"key":"2025061108221029800_ref16","first-page":"87","article-title":"O logice tr\u00f3jwarto\u015bciowej (in polish). ruch filozoficzny 5, 170\u2013171 (1920); english translation: on three-valued logic","volume-title":"Selected Works by Jan \u0141ukasiewicz","author":"\u0141ukasiewicz","year":"1970"},{"key":"2025061108221029800_ref17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2307\/2268660","article-title":"A theorem about infinite-valued sentential logic","volume":"16","author":"McNaughton","year":"1951","journal-title":"Journal of Symbolic Logic"},{"key":"2025061108221029800_ref18","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0304-3975(87)90083-1","article-title":"Satisfiability in many-valued sentential logic is NP-complete","volume":"52","author":"Mundici","year":"1987","journal-title":"Theoretical Computer Science"},{"key":"2025061108221029800_ref19","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/978-94-017-1652-9_8","article-title":"Ulam game, the logic of MaxSAT, and many-valued partitions","volume-title":"Fuzzy Sets, Logics and Reasoning About Knowledge","author":"Mundici","year":"1999"},{"key":"2025061108221029800_ref20","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1007\/978-3-642-02906-6_3","article-title":"Conditionals and independence in many-valued logics","volume-title":"Symbolic and Quantitative Approaches to Reasoning With Uncertainty: 10th European Conference, ECSQARU 2009, Verona, Italy, July 1\u20133, 2009. Proceedings 10","author":"Mundici","year":"2009"},{"key":"2025061108221029800_ref21","doi-asserted-by":"crossref","first-page":"805","DOI":"10.1093\/jigpal\/jzac050","article-title":"Proving properties of binary classification neural networks via \u0141ukasiewicz logic","volume":"31","author":"Preto","year":"2023","journal-title":"Logic Journal of the IGPL"},{"key":"2025061108221029800_ref22","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1109\/ISMVL57333.2023.00039","article-title":"Benchmarking \u0141ukasiewicz logic solvers with properties of neural networks","volume-title":"2023 IEEE 53rd International Symposium on Multiple-Valued Logic (ISMVL)","author":"Preto","year":"2023"},{"key":"2025061108221029800_ref23","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1109\/ISMVL57333.2023.00040","article-title":"Linking \u0141ukasiewicz logic and Boolean maximum satisfiability","volume-title":"2023 IEEE 53rd International Symposium on Multiple-Valued Logic (ISMVL)","author":"Preto","year":"2023"},{"key":"2025061108221029800_ref24","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0004-3702(94)00009-P","article-title":"Tractable reasoning via approximation","volume":"74","author":"Schaerf","year":"1995","journal-title":"Artificial Intelligence"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/35\/5\/exad059\/52058375\/exad059.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/35\/5\/exad059\/52058375\/exad059.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T12:22:24Z","timestamp":1749644544000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/doi\/10.1093\/logcom\/exad059\/7308485"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,13]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,6,11]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exad059","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,7]]},"published":{"date-parts":[[2023,10,13]]},"article-number":"exad059"}}