{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:34:24Z","timestamp":1753889664149,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2012,9,30]],"date-time":"2012-09-30T00:00:00Z","timestamp":1348963200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"funder":[{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"crossref","award":["ANR-09-BLAN-0011"],"award-info":[{"award-number":["ANR-09-BLAN-0011"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We study Boolean circuits as a representation of Boolean functions and\nconsider different equivalence, audit, and enumeration problems. For a number\nof restricted sets of gate types (bases) we obtain efficient algorithms, while\nfor all other gate types we show these problems are at least NP-hard.<\/jats:p>","DOI":"10.2168\/lmcs-8(3:31)2012","type":"journal-article","created":{"date-parts":[[2013,11,29]],"date-time":"2013-11-29T08:17:46Z","timestamp":1385713066000},"source":"Crossref","is-referenced-by-count":2,"title":["Complexity classifications for different equivalence and audit problems for Boolean circuits"],"prefix":"10.46298","volume":"Volume 8, Issue 3","author":[{"given":"Elmar","family":"B\u00c3\u00b6hler","sequence":"first","affiliation":[]},{"given":"Nadia","family":"Creignou","sequence":"additional","affiliation":[]},{"given":"Matthias","family":"Galota","sequence":"additional","affiliation":[]},{"given":"Steffen","family":"Reith","sequence":"additional","affiliation":[]},{"given":"Henning","family":"Schnoor","sequence":"additional","affiliation":[]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2012,9,30]]},"reference":[{"key":"665:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1172\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1172\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:05:27Z","timestamp":1681243527000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1172"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,30]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-8(3:31)2012","relation":{"is-same-as":[{"id-type":"arxiv","id":"1009.1208","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1009.1208","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2012,9,30]]},"article-number":"1172"}}