{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T07:14:20Z","timestamp":1761549260838,"version":"build-2065373602"},"reference-count":7,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2022,4,26]],"date-time":"2022-04-26T00:00:00Z","timestamp":1650931200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SAT"],"abstract":"<jats:p>It is shown that disjunction of two switch-lists can blow up the representation size exponentially. Since switch-lists can be negated without any increase in size, this shows that conjunction of switch-lists also leads to an exponential blow-up in general.<\/jats:p>","DOI":"10.3233\/sat-220002","type":"journal-article","created":{"date-parts":[[2022,4,26]],"date-time":"2022-04-26T13:29:25Z","timestamp":1650979765000},"page":"1-4","source":"Crossref","is-referenced-by-count":1,"title":["No Efficient Disjunction or Conjunction of Switch-Lists"],"prefix":"10.1177","volume":"13","author":[{"given":"Stefan","family":"Mengel","sequence":"first","affiliation":[{"name":"Universit\u00e9\u00a0d\u2019Artois, CNRS, Centre de Recherche en Informatique de Lens (CRIL), Lens, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2022,4,26]]},"reference":[{"key":"10.3233\/SAT-220002_ref1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.disopt.2016.11.002","article-title":"Recognition of tractable DNFs representable by a constant number of intervals","volume":"23","author":"\u010cepek","year":"2017","journal-title":"Discret. Optim."},{"key":"10.3233\/SAT-220002_ref2","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1613\/jair.1.12199","article-title":"Properties of switch-list representations of Boolean functions","volume":"69","author":"Chrom\u00fd","year":"2020","journal-title":"J. Artif. Intell. Res."},{"key":"10.3233\/SAT-220002_ref3","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1613\/jair.989","article-title":"A knowledge compilation map","volume":"17","author":"Darwiche","year":"2002","journal-title":"J. Artif. Intell. Res."},{"key":"10.3233\/SAT-220002_ref4","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.artint.2014.07.004","article-title":"Disjunctive closures for knowledge compilation","volume":"216","author":"Fargier","year":"2014","journal-title":"Artif. Intell."},{"key":"10.3233\/SAT-220002_ref5","unstructured":"H.\u00a0Fargier, P.\u00a0Marquis and A.\u00a0Niveau, Towards a knowledge compilation map for heterogeneous representation languages, in: IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3\u20139, 2013, F.\u00a0Rossi, ed., IJCAI\/AAAI, 2013, pp.\u00a0877\u2013883, https:\/\/www.ijcai.org\/Proceedings\/13\/Papers\/135.pdf."},{"key":"10.3233\/SAT-220002_ref6","unstructured":"K.\u00a0Pipatsrisawat and A.\u00a0Darwiche, New compilation languages based on structured decomposability, in: Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, AAAI 2008, Chicago, Illinois, USA, July 13\u201317, 2008, D.\u00a0Fox and C.P.\u00a0Gomes, eds, AAAI Press, pp.\u00a0517\u2013522, http:\/\/www.aaai.org\/Library\/AAAI\/2008\/aaai08-082.php."},{"issue":"1\u20133","key":"10.3233\/SAT-220002_ref7","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.dam.2004.08.009","article-title":"Computing the minimum DNF representation of Boolean functions defined by intervals","volume":"149","author":"Schieber","year":"2005","journal-title":"Discret. Appl. Math."}],"container-title":["Journal on Satisfiability, Boolean Modeling and Computation"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/SAT-220002","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T07:08:26Z","timestamp":1761548906000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/SAT-220002"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,26]]},"references-count":7,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,4,26]]}},"URL":"https:\/\/doi.org\/10.3233\/sat-220002","relation":{},"ISSN":["1574-0617"],"issn-type":[{"type":"electronic","value":"1574-0617"}],"subject":[],"published":{"date-parts":[[2022,4,26]]}}}