{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T15:55:38Z","timestamp":1762876538879,"version":"3.44.0"},"reference-count":51,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","funder":[{"name":"the ARC Discovery Project","award":["DP1094578"],"award-info":[{"award-number":["DP1094578"]}]},{"name":"ARC Future Fellowship","award":["FT120100666"],"award-info":[{"award-number":["FT120100666"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:p> In this paper, we examine some flexible notions of constraint satisfaction, observing some relationships between model theoretic notions of universal Horn class membership and robust satisfiability. We show the NP-completeness of 2-robust positive 1-in-3SAT in order to give very small examples of finite algebras with NP-hard variety membership problem. In particular, we give a 3-element algebra with this property, and solve a widely stated problem by showing that the 6-element Brandt monoid has NP-hard variety membership problem. These are the smallest possible sizes for a general algebra and a semigroup to exhibit NP-hardness for the membership problem of finite algebras in finitely generated varieties. <\/jats:p>","DOI":"10.1142\/s0218196725500225","type":"journal-article","created":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T10:42:43Z","timestamp":1748601763000},"page":"771-821","source":"Crossref","is-referenced-by-count":1,"title":["Flexible constraint satisfiability and a problem in semigroup theory"],"prefix":"10.1142","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8149-1141","authenticated-orcid":false,"given":"Marcel","family":"Jackson","sequence":"first","affiliation":[{"name":"Department of Mathematical and Physical Sciences, La Trobe University, Victoria 3086, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2025,7,3]]},"reference":[{"key":"S0218196725500225BIB001","first-page":"440","volume-title":"Proc. Twenty-Third Int. Joint Conf. Artificial Intelligence","author":"Abramsky S.","year":"2013"},{"volume-title":"Finite Semigroups and Universal Algebra","year":"1994","author":"Almeida J.","key":"S0218196725500225BIB002"},{"key":"S0218196725500225BIB003","doi-asserted-by":"publisher","DOI":"10.1145\/3457606"},{"key":"S0218196725500225BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.05.003"},{"key":"S0218196725500225BIB006","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798345944"},{"key":"S0218196725500225BIB007","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.117"},{"key":"S0218196725500225BIB008","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"S0218196725500225BIB009","first-page":"1","volume":"11","author":"Bul\u00edn J.","year":"2015","journal-title":"Log. Methods Comp. Sci."},{"key":"S0218196725500225BIB010","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316300"},{"key":"S0218196725500225BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8130-3"},{"key":"S0218196725500225BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00164-5"},{"key":"S0218196725500225BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(76)90029-3"},{"key":"S0218196725500225BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9326-7"},{"key":"S0218196725500225BIB015","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703425848"},{"key":"S0218196725500225BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/11685654_12"},{"volume-title":"Algebraic Theory of Quasivarieties","year":"1998","author":"Gorbunov V. A.","key":"S0218196725500225BIB017"},{"key":"S0218196725500225BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23786-7_26"},{"key":"S0218196725500225BIB019","doi-asserted-by":"publisher","DOI":"10.1137\/0217018"},{"key":"S0218196725500225BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/s00233-022-10336-9"},{"key":"S0218196725500225BIB021","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"36:1","volume-title":"27th International Symposium on Algorithms and Computation (ISAAC 2016)","volume":"64","author":"Ham L.","year":"2016"},{"key":"S0218196725500225BIB022","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.03.006"},{"key":"S0218196725500225BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66158-2_10"},{"key":"S0218196725500225BIB024","first-page":"108","volume":"85","author":"Hayes B.","year":"1997","journal-title":"Amer. Sci."},{"key":"S0218196725500225BIB025","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198511946.001.0001"},{"key":"S0218196725500225BIB026","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"S0218196725500225BIB027","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1208358744"},{"key":"S0218196725500225BIB028","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196706002846"},{"key":"S0218196725500225BIB029","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-011-0126-3"},{"key":"S0218196725500225BIB030","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2022.07.042"},{"key":"S0218196725500225BIB031","doi-asserted-by":"publisher","DOI":"10.1007\/s11225-012-9372-4"},{"key":"S0218196725500225BIB032","doi-asserted-by":"publisher","DOI":"10.1007\/s00233-021-10180-3"},{"key":"S0218196725500225BIB033","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574274"},{"key":"S0218196725500225BIB034","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196795000227"},{"key":"S0218196725500225BIB035","doi-asserted-by":"publisher","DOI":"10.1007\/s00233-009-9180-y"},{"key":"S0218196725500225BIB037","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196707004335"},{"key":"S0218196725500225BIB038","doi-asserted-by":"publisher","DOI":"10.1137\/070680801"},{"key":"S0218196725500225BIB039","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.048"},{"key":"S0218196725500225BIB040","doi-asserted-by":"publisher","DOI":"10.1112\/S1461157014000412"},{"key":"S0218196725500225BIB041","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1951-0044470-3"},{"key":"S0218196725500225BIB042","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196708004913"},{"key":"S0218196725500225BIB043","doi-asserted-by":"publisher","DOI":"10.1038\/22055"},{"key":"S0218196725500225BIB044","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(74)90008-5"},{"key":"S0218196725500225BIB045","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90062-6"},{"key":"S0218196725500225BIB046","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100017436"},{"key":"S0218196725500225BIB048","doi-asserted-by":"publisher","DOI":"10.1007\/s00233-010-9268-4"},{"key":"S0218196725500225BIB049","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196702001085"},{"key":"S0218196725500225BIB050","doi-asserted-by":"publisher","DOI":"10.1017\/S0004972710000420"},{"key":"S0218196725500225BIB051","doi-asserted-by":"publisher","DOI":"10.1007\/s11225-005-0356-5"},{"key":"S0218196725500225BIB052","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-021-00731-8"},{"key":"S0218196725500225BIB054","first-page":"289","volume":"250","author":"Wheeler W.","year":"1979","journal-title":"Trans. Amer. Math. Soc."},{"key":"S0218196725500225BIB055","doi-asserted-by":"publisher","DOI":"10.1017\/S0004972711002541"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196725500225","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T03:08:27Z","timestamp":1756436907000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0218196725500225"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,3]]},"references-count":51,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["10.1142\/S0218196725500225"],"URL":"https:\/\/doi.org\/10.1142\/s0218196725500225","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"type":"print","value":"0218-1967"},{"type":"electronic","value":"1793-6500"}],"subject":[],"published":{"date-parts":[[2025,7,3]]}}}