{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T19:35:54Z","timestamp":1774380954821,"version":"3.50.1"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2006,4,1]],"date-time":"2006-04-01T00:00:00Z","timestamp":1143849600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2006,4]]},"abstract":"<jats:p>\n            A theorem by Lin and Zhao shows how to turn any nondisjunctive logic program, understood in accordance with the answer set semantics, into an equivalent set of propositional formulas. The set of formulas generated by this process can be significantly larger than the original program. In this article we show (assuming\n            <jats:italic>P<\/jats:italic>\n            \u2288\n            <jats:italic>NC<\/jats:italic>\n            <jats:sup>1<\/jats:sup>\n            \/\n            <jats:italic>poly<\/jats:italic>\n            , a conjecture from the theory of computational complexity that is widely believed to be true) that this is inevitable: any equivalent translation from logic programs to propositional formulas involves a significant increase in size.\n          <\/jats:p>","DOI":"10.1145\/1131313.1131316","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"261-268","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":68,"title":["Why are there so many loop formulas?"],"prefix":"10.1145","volume":"7","author":[{"given":"Vladimir","family":"Lifschitz","sequence":"first","affiliation":[{"name":"University of Texas at Austin, Austin, TX"}]},{"given":"Alexander","family":"Razborov","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study, Princeton, NJ"}]}],"member":"320","published-online":{"date-parts":[[2006,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","volume-title":"Negation as failure","author":"Clark K.","DOI":"10.1007\/978-1-4684-3384-5_11"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80046-2"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the International Logic Programming Symposium (ILPS), D. Miller, ed. 266--278","author":"Eiter T."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the International Logic Programming Conference and Symposium. R. Kowalski and K. Bowen, eds. 1070--1080","author":"Gelfond M."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). 862--869","author":"Gogic G."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/203244"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(97)10001-2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80050-X"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the International Conference on Logic Programming (ICLP). 451--465","author":"Lee J."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018978005636"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). 853--864","author":"Lin F."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the National Conference on Artificial Intelligence (AAAI). 112--117","author":"Lin F."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116836"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00187-X"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(80)90014-4"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 4th Hawaii Symposium on System Sciences. Western Periodicals Company, North Hollywood, 525--527","author":"Spira P. M.","year":"1971"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1131313.1131316","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1131313.1131316","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:16Z","timestamp":1750259176000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1131313.1131316"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,4]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,4]]}},"alternative-id":["10.1145\/1131313.1131316"],"URL":"https:\/\/doi.org\/10.1145\/1131313.1131316","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,4]]},"assertion":[{"value":"2006-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}