{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T07:37:37Z","timestamp":1723016257256},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,8]]},"abstract":"<jats:p>A Boolean formula in conjunctive normal form (CNF) is called matched if the system of sets of variables which appear in individual clauses has a system of distinct representatives. We present here two results for matched CNFs: The first result is a shorter and simpler proof of the fact that Boolean minimization remains complete for the second level of polynomial hierarchy even if the input is restricted to matched CNFs. The second result is structural --- we show that  if a Boolean function f admits a representation by a matched CNF then every clause minimum CNF representation of f is matched.<\/jats:p>","DOI":"10.24963\/ijcai.2017\/706","type":"proceedings-article","created":{"date-parts":[[2017,7,28]],"date-time":"2017-07-28T05:14:07Z","timestamp":1501218847000},"page":"4980-4984","source":"Crossref","is-referenced-by-count":0,"title":["On Minimum Representations of Matched Formulas (Extended Abstract)"],"prefix":"10.24963","author":[{"given":"Ond\u0159ej","family":"\u010cepek","sequence":"first","affiliation":[{"name":"Charles University, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u0160tefan","family":"Gursk\u00fd","sequence":"additional","affiliation":[{"name":"Charles University, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr","family":"Ku\u010dera","sequence":"additional","affiliation":[{"name":"Charles University, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"number":"26","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)","University of Technology Sydney (UTS)","Australian Computer Society (ACS)"],"acronym":"IJCAI-2017","name":"Twenty-Sixth International Joint Conference on Artificial Intelligence","start":{"date-parts":[[2017,8,19]]},"theme":"Artificial Intelligence","location":"Melbourne, Australia","end":{"date-parts":[[2017,8,26]]}},"container-title":["Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2017,7,28]],"date-time":"2017-07-28T07:55:13Z","timestamp":1501228513000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2017\/706"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2017,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2017\/706","relation":{},"subject":[],"published":{"date-parts":[[2017,8]]}}}