{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:06:11Z","timestamp":1750309571149,"version":"3.41.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T00:00:00Z","timestamp":1727740800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Sponsor National Social Science Fund of China","award":["#14CZX058"],"award-info":[{"award-number":["#14CZX058"]}]},{"name":"Sponsor Guangdong Basic and Applied Basic Research Foundation","award":["#2023A1515010892"],"award-info":[{"award-number":["#2023A1515010892"]}]},{"name":"Sponsor National Key Research Institutes for the Humanities and Social Sciences","award":["#19JJD720002"],"award-info":[{"award-number":["#19JJD720002"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2024,10,31]]},"abstract":"<jats:p>\n            Showing that a problem is\n            <jats:italic>hard<\/jats:italic>\n            for a model of computation is one of the most challenging tasks in theoretical computer science, logic and mathematics. For example, it remains beyond reach to find an\n            <jats:italic>explicit<\/jats:italic>\n            problem that cannot be computed by polynomial size propositional formulas (PF). As a model of computation, logic programs (LP) under answer set semantics are as expressive as PF and also\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathtt{NP}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -complete for satisfiability checking. In this article, we show that the PAR problem is hard for LP, i.e., deciding whether a binary string contains an odd number of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(1\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            \u2019s requires\n            <jats:italic>exponential<\/jats:italic>\n            size LP. The proof idea is first to transform logic programs into equivalent boolean circuits and then apply a probabilistic method known as\n            <jats:italic>random restriction<\/jats:italic>\n            to obtain an exponential lower bound. Based on the main result, we generalize a sufficient condition for identifying hard problems for LP and give a separation map for an LP family from a computational point of view, whose members are all equally expressive and share the same reasoning complexity.\n          <\/jats:p>","DOI":"10.1145\/3676964","type":"journal-article","created":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T17:45:49Z","timestamp":1720633549000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Computationally Hard Problems for Logic Programs under Answer Set Semantics"],"prefix":"10.1145","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-3698-6381","authenticated-orcid":false,"given":"Yuping","family":"Shen","sequence":"first","affiliation":[{"name":"Institute of Logic and Cognition, Department of Philosophy, Sun Yat-sen University, Guangzhou, P. R. China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-9333-4406","authenticated-orcid":false,"given":"Xishun","family":"Zhao","sequence":"additional","affiliation":[{"name":"Institute of Logic and Cognition, Department of Philosophy, Sun Yat-sen University, Guangzhou, P. R. China"}]}],"member":"320","published-online":{"date-parts":[[2024,10]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"Foundations of Databases: The Logical Level","author":"Abiteboul Serge","year":"1995","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases: The Logical Level (1st ed.). Addison-Wesley Longman Publishing Co., Inc., USA.","edition":"1"},{"key":"e_1_3_2_3_2","volume-title":"The Probabilistic Method","author":"Alon Noga","year":"2016","unstructured":"Noga Alon and Joel H. Spencer. 2016. The Probabilistic Method (4th ed.). Wiley Publishing, New York.","edition":"4"},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"Arora Sanjeev","year":"2009","unstructured":"Sanjeev Arora and Boaz Barak. 2009. Computational Complexity: A Modern Approach (1st ed.). Cambridge University Press, USA.","edition":"1"},{"key":"e_1_3_2_5_2","volume-title":"Knowledge Representation, Reasoning and Declarative Problem Solving","author":"Baral Chitta","year":"2010","unstructured":"Chitta Baral. 2010. Knowledge Representation, Reasoning and Declarative Problem Solving (1st ed.). Cambridge University Press, USA.","edition":"1"},{"key":"e_1_3_2_6_2","series-title":"Frontiers in Artificial Intelligence and Applications","doi-asserted-by":"crossref","DOI":"10.3233\/FAIA336","volume-title":"Handbook of Satisfiability","author":"Biere Armin","year":"2021","unstructured":"Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh (Eds.). 2021. Handbook of Satisfiability (2nd ed.). Frontiers in Artificial Intelligence and Applications, Vol. 336. IOS Press. DOI: 10.3233\/FAIA336","edition":"2"},{"issue":"12","key":"e_1_3_2_7_2","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1145\/2043174.2043195","article-title":"Answer set programming at a glance","volume":"54","author":"Brewka Gerhard","year":"2011","unstructured":"Gerhard Brewka, Thomas Eiter, and Miroslaw Truszczynski. 2011. Answer set programming at a glance. Commun. ACM 54, 12 (2011), 92\u2013103.","journal-title":"Commun. ACM"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/0213028"},{"key":"e_1_3_2_9_2","first-page":"292","volume-title":"Logic and Data Bases","author":"Clark Keith L.","year":"1978","unstructured":"Keith L. Clark. 1978. Negation as failure. In Logic and Data Bases. H. Gallaire and J. Minker (Eds.), Plenum Press, New York, NY, 292\u2013322."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04943-3"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80046-2"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"e_1_3_2_13_2","first-page":"203","volume-title":"Proceedings of the 9th International Conference on Principles of Knowledge Representation and Reasoning (KR\u201904)","author":"Coste-Marquis Sylvie","year":"2004","unstructured":"Sylvie Coste-Marquis, J\u00e9r\u00f4me Lang, Paolo Liberatore, and Pierre Marquis. 2004. Expressive power and succinctness of propositional languages for preference representation. In Proceedings of the 9th International Conference on Principles of Knowledge Representation and Reasoning (KR\u201904). AAAI Press, 203\u2013212."},{"key":"e_1_3_2_14_2","volume-title":"Elements of Information Theory","author":"Cover Thomas M.","year":"2006","unstructured":"Thomas M. Cover and Joy A. Thomas. 2006. Elements of Information Theory. Wiley-Interscience, USA."},{"issue":"3","key":"e_1_3_2_15_2","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1145\/502807.502810","article-title":"Complexity and expressive power of logic programming","volume":"33","author":"Dantsin Evgeny","year":"2001","unstructured":"Evgeny Dantsin, Thomas Eiter, Georg Gottlob, and Andrei Voronkov. 2001. Complexity and expressive power of logic programming. Comput. Surveys 33, 3 (Sep. 2001), 374\u2013425.","journal-title":"Comput. Surveys"},{"key":"e_1_3_2_16_2","first-page":"74","volume-title":"Logic Programming and Nonmonotonic Reasoning","author":"Do\u011fanda\u011f Semra","year":"2004","unstructured":"Semra Do\u011fanda\u011f, Paolo Ferraris, and Vladimir Lifschitz. 2004. Almost definite causal theories. In Logic Programming and Nonmonotonic Reasoning. Vladimir Lifschitz and Ilkka Niemel\u00e4 (Eds.), Springer, Berlin, 74\u201386."},{"issue":"4","key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1017\/S1471068403001765","article-title":"Tight logic programs","volume":"3","author":"Erdem Esra","year":"2003","unstructured":"Esra Erdem and Vladimir Lifschitz. 2003. Tight logic programs. Theory Pract. Logic Program. 3, 4 (Jul. 2003), 499\u2013518.","journal-title":"Theory Pract. Logic Program"},{"key":"e_1_3_2_18_2","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s10472-006-9025-2","article-title":"A generalization of the Lin-Zhao theorem","volume":"47","author":"Ferraris Paolo","year":"2006","unstructured":"Paolo Ferraris, Joohyung Lee, and Vladimir Lifschitz. 2006. A generalization of the Lin-Zhao theorem. Ann. Math. Artif. Intell. 47 (2006), 79\u2013101. Retrieved from http:\/\/www.cs.utexas.edu\/users\/ai-lab?fer06","journal-title":"Ann. Math. Artif. Intell."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068403001923"},{"key":"e_1_3_2_20_2","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.artint.2013.02.003","article-title":"On the succinctness of some modal logics","volume":"197","author":"French Tim","year":"2013","unstructured":"Tim French, Wiebe van der Hoek, Petar Iliev, and Barteld P. Kooi. 2013. On the succinctness of some modal logics. Artif. Intell. 197 (2013), 56\u201385.","journal-title":"Artif. Intell."},{"issue":"1","key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","article-title":"Parity, circuits, and the polynomial-time hierarchy","volume":"17","author":"Furst Merrick L.","year":"1984","unstructured":"Merrick L. Furst, James B. Saxe, and Michael Sipser. 1984. Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory 17, 1 (1984), 13\u201327.","journal-title":"Math. Syst. Theory"},{"key":"e_1_3_2_22_2","volume-title":"Answer Set Solving in Practice","author":"Gebser Martin","year":"2012","unstructured":"Martin Gebser, Roland Kaminski, Benjamin Kaufmann, and Torsten Schaub. 2012. Answer Set Solving in Practice. Morgan & Claypool Publishers, Lexington, KY."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068411000019"},{"key":"e_1_3_2_24_2","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/11546207_5","volume-title":"Logic Programming and Nonmonotonic Reasoning","author":"Gebser Martin","year":"2005","unstructured":"Martin Gebser and Torsten Schaub. 2005. Loops: Relevant or redundant? In Logic Programming and Nonmonotonic Reasoning. Chitta Baral, Gianluigi Greco, Nicola Leone, and Giorgio Terracina (Eds.), Springer, Berlin, 53\u201365."},{"key":"e_1_3_2_25_2","first-page":"1070","volume-title":"Proceedings of International Logic Programming Conference and Symposium","author":"Gelfond Michael","year":"1988","unstructured":"Michael Gelfond and Vladimir Lifschitz. 1988. The stable model semantics for logic programming. In Proceedings of International Logic Programming Conference and Symposium. Kowalski R. and Bowen K. (Eds.), MIT Press, USA, 1070\u20131080."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2002.12.001"},{"key":"e_1_3_2_27_2","first-page":"862","volume-title":"Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI \u201995)","volume":"1","author":"Gogic Goran","year":"1995","unstructured":"Goran Gogic, Henry Kautz, Christos Papadimitriou, and Bart Selman. 1995. The comparative linguistics of knowledge representation. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI \u201995), Vol. 1. Morgan Kaufmann Publishers Inc., San Francisco, CA, 862\u2013869."},{"key":"e_1_3_2_28_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804106","volume-title":"Computational Complexity: A Conceptual Perspective","author":"Goldreich Oded","year":"2008","unstructured":"Oded Goldreich. 2008. Computational Complexity: A Conceptual Perspective (1 ed.). Cambridge University Press, USA.","edition":"1"},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to Parallel Computation: P-Completeness Theory","author":"Greenlaw Raymond","year":"1995","unstructured":"Raymond Greenlaw, H. James Hoover, and Walter L. Ruzzo. 1995. Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, UK."},{"key":"e_1_3_2_30_2","first-page":"438","volume-title":"Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS \u201904)","author":"Grohe Martin","year":"2004","unstructured":"Martin Grohe and Nicole Schweikardt. 2004. The succinctness of first-order logic on linear orders. In Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS \u201904). IEEE, 438\u2013447. DOI: 10.1109\/LICS.2004.1319638"},{"key":"e_1_3_2_31_2","first-page":"6","volume-title":"Proceedings of the 18th Annual ACM Symposium on Theory of computing (STOC \u201986)","author":"H\u00e5stad Johan","year":"1986","unstructured":"Johan H\u00e5stad. 1986. Almost optimal lower bounds for small depth circuits. In Proceedings of the 18th Annual ACM Symposium on Theory of computing (STOC \u201986). ACM, New York, NY, 6\u201320."},{"key":"e_1_3_2_32_2","volume-title":"Computational Limitations of Small-Depth Circuits","author":"H\u00e5stad Johan","year":"1987","unstructured":"Johan H\u00e5stad. 1987. Computational Limitations of Small-Depth Circuits. MIT Press, Cambridge, MA, USA."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/0216051"},{"key":"e_1_3_2_34_2","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-24508-4","volume-title":"Boolean Function Complexity: Advances and Frontiers","author":"Jukna Stasys","year":"2012","unstructured":"Stasys Jukna. 2012. Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics, Vol. 27. Springer, Berlin. DOI: 10.1007\/978-3-642-24508-4"},{"key":"e_1_3_2_35_2","first-page":"503","volume-title":"Proceedings of the 19th International Joint Conference on Artificial Intelligence","author":"Lee Joohyung","year":"2005","unstructured":"Joohyung Lee. 2005. A model-theoretic counterpart of loop formulas. In Proceedings of the 19th International Joint Conference on Artificial Intelligence. Morgan Kaufmann Publishers Inc., Edinburgh, 503\u2013508."},{"key":"e_1_3_2_36_2","first-page":"451","volume-title":"Logic Programming","author":"Lee Joohyung","year":"2003","unstructured":"Joohyung Lee and Vladimir Lifschitz. 2003. Loop formulas for disjunctive logic programs. In Logic Programming. Catuscia Palamidessi (Ed.), Springer, Berlin, 451\u2013465."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-016-9257-7"},{"key":"e_1_3_2_38_2","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1023\/A:1018978005636","article-title":"Nested expressions in logic programs","volume":"25","author":"Lifschitz Vladimir","year":"1999","unstructured":"Vladimir Lifschitz. 1999. Nested expressions in logic programs. Annals of Mathematics and Artificial Intelligence 25 (1999), 369\u2013389.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"e_1_3_2_39_2","first-page":"1594","volume-title":"Proceedings of the 23rd National Conference on Artificial Intelligence","volume":"3","author":"Lifschitz Vladimir","year":"2008","unstructured":"Vladimir Lifschitz. 2008. What is answer set programming? In Proceedings of the 23rd National Conference on Artificial Intelligence, Vol. 3. AAAI Press, Chicago, IL, 1594\u20131597."},{"key":"e_1_3_2_40_2","first-page":"259","volume-title":"Proceedings of the Technical Communications of the 28th International Conference on Logic Programming","author":"Lifschitz Vladimir","year":"2012","unstructured":"Vladimir Lifschitz. 2012. Two-valued logic programs. In Proceedings of the Technical Communications of the 28th International Conference on Logic Programming. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 259\u2013266."},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-24658-7"},{"issue":"2","key":"e_1_3_2_42_2","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/1131313.1131316","article-title":"Why are there so many loop formulas?","volume":"7","author":"Lifschitz Vladimir","year":"2006","unstructured":"Vladimir Lifschitz and Alexander Razborov. 2006. Why are there so many loop formulas? ACM Trans. Comput. Log. 7, 2 (Apr. 2006), 261\u2013268.","journal-title":"ACM Trans. Comput. Log."},{"issue":"1","key":"e_1_3_2_43_2","first-page":"115","article-title":"ASSAT: Computing answer sets of a logic program by SAT solvers","volume":"157","author":"Lin Fangzhen","year":"2004","unstructured":"Fangzhen Lin and Yuting Zhao. 2004. ASSAT: Computing answer sets of a logic program by SAT solvers. Artif. Intell. 157, 1\u20132 (2004), 115\u2013137.","journal-title":"Artif. Intell."},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60085-2_17"},{"key":"e_1_3_2_45_2","volume-title":"Causality in Commonsense Reasoning about Actions","author":"McCain Norman","year":"1997","unstructured":"Norman McCain. 1997. Causality in Commonsense Reasoning about Actions. Ph.D. Dissertation. University of Texas at Austin."},{"key":"e_1_3_2_46_2","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1023\/A:1018930122475","article-title":"Logic programs with stable model semantics as a constraint programming paradigm","volume":"25","author":"Niemel\u00e4 Ilkka","year":"1999","unstructured":"Ilkka Niemel\u00e4. 1999. Logic programs with stable model semantics as a constraint programming paradigm. Ann. Math. Artif. Intell. 25 (1999), 241\u2013273.","journal-title":"Ann. Math. Artif. Intell."},{"key":"e_1_3_2_47_2","volume-title":"Computational Complexity","author":"Papadimitriou Christos H.","year":"1994","unstructured":"Christos H. Papadimitriou. 1994. Computational Complexity. Addison-Wesley, USA."},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1002\/sapm194221183"},{"key":"e_1_3_2_50_2","volume-title":"Models of Computation: Exploring the Power of Computing","author":"Savage John E.","year":"1997","unstructured":"John E. Savage. 1997. Models of Computation: Exploring the Power of Computing (1st ed.). Addison-Wesley Longman Publishing Co., Inc., USA.","edition":"1"},{"key":"e_1_3_2_51_2","first-page":"665\u2013668","volume-title":"Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR\u201914)","author":"Shen Yuping","year":"2014","unstructured":"Yuping Shen and Xishun Zhao. 2014. Canonical logic programs are succinctly incomparable with propositional formulas. In Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR\u201914). AAAI Press, Vienna, 665\u2013668."},{"issue":"1","key":"e_1_3_2_52_2","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0004-3702(02)00187-X","article-title":"Extending and implementing the stable model semantics","volume":"138","author":"Simons Patrik","year":"2002","unstructured":"Patrik Simons, Ilkka Niemel\u00e4, and Timo Soininen. 2002. Extending and implementing the stable model semantics. Artif. Intell. 138, 1\u20132 (2002), 181\u2013234.","journal-title":"Artif. Intell."},{"key":"e_1_3_2_53_2","first-page":"61","volume-title":"Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC \u201983)","author":"Sipser Michael","year":"1983","unstructured":"Michael Sipser. 1983. Borel sets and circuit complexity. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC \u201983). ACM, New York, NY, 61\u201369. DOI: 10.1145\/800061.808733"},{"key":"e_1_3_2_54_2","volume-title":"Introduction to the Theory of Computation","author":"Sipser Michael","year":"2013","unstructured":"Michael Sipser. 2013. Introduction to the Theory of Computation (3rd ed.). Course Technology, Boston, MA.","edition":"3"},{"key":"e_1_3_2_55_2","first-page":"525","volume-title":"Proceedings of the 4th Hawaii Symposium on System Sciences","author":"Spira Philip","year":"1971","unstructured":"Philip Spira. 1971. On time-hardware complexity tradeoffs for Boolean functions. In Proceedings of the 4th Hawaii Symposium on System Sciences. Western Periodicals Company, North Hollywood, 525\u2013527."},{"key":"e_1_3_2_56_2","volume-title":"Handbook of Knowledge Representation","author":"Harmelen Frank van","year":"2007","unstructured":"Frank van Harmelen, Frank van Harmelen, Vladimir Lifschitz, and Bruce Porter. 2007. Handbook of Knowledge Representation. Elsevier Science, San Diego, CA."},{"key":"e_1_3_2_57_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity: A Uniform Approach","author":"Vollmer Heribert","year":"1999","unstructured":"Heribert Vollmer. 1999. Introduction to Circuit Complexity: A Uniform Approach. Springer-Verlag New York, Inc., Secaucus, NJ."},{"key":"e_1_3_2_58_2","volume-title":"The Complexity of Boolean Functions","author":"Wegener Ingo","year":"1987","unstructured":"Ingo Wegener. 1987. The Complexity of Boolean Functions (1st ed.). John Wiley & Sons, Inc., USA.","edition":"1"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/2559903"},{"key":"e_1_3_2_60_2","first-page":"859","volume-title":"Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI \u201903)","author":"You Jia-Huai","year":"2003","unstructured":"Jia-Huai You, Li-Yan Yuan, and Mingyi Zhang. 2003. On the equivalence between answer sets and models of completion for nested logic programs. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI \u201903). Morgan Kaufmann Publishers Inc., San Francisco, CA, 859\u2013864."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3676964","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3676964","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:19:13Z","timestamp":1750295953000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3676964"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10]]},"references-count":59,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,10,31]]}},"alternative-id":["10.1145\/3676964"],"URL":"https:\/\/doi.org\/10.1145\/3676964","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2024,10]]},"assertion":[{"value":"2023-08-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-13","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}