{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:39Z","timestamp":1759637919706},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"06","license":[{"start":{"date-parts":[[2019,3,8]],"date-time":"2019-03-08T00:00:00Z","timestamp":1552003200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2019,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We propose and study a probabilistic logic over an algebraic basis, including equations and domain restrictions. The logic combines aspects from classical logic and equational logic with an exogenous approach to quantitative probabilistic reasoning. We present a sound and weakly complete axiomatization for the logic, parameterized by an equational specification of the algebraic basis coupled with the intended domain restrictions.We show that the satisfiability problem for the logic is decidable, under the assumption that its algebraic basis is given by means of a convergent rewriting system, and, additionally, that the axiomatization of domain restrictions enjoys a suitable subterm property. For this purpose, we provide a polynomial reduction to Satisfiability Modulo Theories. As a consequence, we get that validity in the logic is also decidable. Furthermore, under the assumption that the rewriting system that defines the equational basis underlying the logic is also subterm convergent, we show that the resulting satisfiability problem is NP-complete, and thus the validity problem is coNP-complete.We test the logic with meaningful examples in information security, namely by verifying and estimating the probability of the existence of offline guessing attacks to cryptographic protocols.<\/jats:p>","DOI":"10.1017\/s096012951800035x","type":"journal-article","created":{"date-parts":[[2019,3,8]],"date-time":"2019-03-08T10:52:12Z","timestamp":1552042332000},"page":"872-895","source":"Crossref","is-referenced-by-count":1,"title":["Probabilistic logic over equations and domain restrictions"],"prefix":"10.1017","volume":"29","author":[{"given":"Andreia","family":"Mordido","sequence":"first","affiliation":[]},{"given":"Carlos","family":"Caleiro","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,3,8]]},"reference":[{"key":"S096012951800035X_ref18","first-page":"528","author":"Finger","year":"2011","journal-title":"IJCAI"},{"key":"S096012951800035X_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47709-0_4"},{"key":"S096012951800035X_ref16","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056650"},{"key":"S096012951800035X_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0012855"},{"key":"S096012951800035X_ref9","first-page":"908","volume-title":"Proceedings of the 26th International Joint Conference on Artificial Intelligence","author":"Caleiro","year":"2017"},{"key":"S096012951800035X_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-010-9187-9"},{"key":"S096012951800035X_ref7","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2015.39"},{"key":"S096012951800035X_ref12","first-page":"363","volume-title":"European Symposium on Research in Computer Security","volume":"8134","author":"Conchinha","year":"2013"},{"key":"S096012951800035X_ref19","doi-asserted-by":"publisher","DOI":"10.1109\/49.223865"},{"key":"S096012951800035X_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73368-3_36"},{"key":"S096012951800035X_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19751-2_3"},{"key":"S096012951800035X_ref5","first-page":"16","volume-title":"Proceedings of 12th ACM Conference on Computer and Communications Security","author":"Baudet","year":"2005"},{"key":"S096012951800035X_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2017.04.004"},{"key":"S096012951800035X_ref4","volume-title":"Term Rewriting and All That","author":"Baader","year":"1999"},{"key":"S096012951800035X_ref3","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/2810103.2813707","volume-title":"Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security","author":"Adrian","year":"2015"},{"key":"S096012951800035X_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.08.032"},{"key":"S096012951800035X_ref1","doi-asserted-by":"publisher","DOI":"10.1109\/CSFW.2005.14"},{"key":"S096012951800035X_ref28","first-page":"158","volume":"10","author":"Van Eijck","year":"2014","journal-title":"Advances in Modal Logic"},{"key":"S096012951800035X_ref27","volume-title":"Mathematical logic","author":"Shoenfield","year":"2010"},{"key":"S096012951800035X_ref25","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217859"},{"key":"S096012951800035X_ref22","first-page":"165","volume":"1","author":"Mateus","year":"2005","journal-title":"Essays on the Foundations of Mathematics and Logic"},{"key":"S096012951800035X_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2009.10.010"},{"key":"S096012951800035X_ref20","doi-asserted-by":"publisher","DOI":"10.2307\/2267044"},{"key":"S096012951800035X_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90060-U"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096012951800035X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,13]],"date-time":"2022-09-13T10:57:41Z","timestamp":1663066661000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096012951800035X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,8]]},"references-count":24,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["S096012951800035X"],"URL":"https:\/\/doi.org\/10.1017\/s096012951800035x","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,8]]}}}