{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:08:34Z","timestamp":1750306114355,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,4,30]],"date-time":"2017-04-30T00:00:00Z","timestamp":1493510400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences","award":["SYSKF1506"],"award-info":[{"award-number":["SYSKF1506"]}]},{"DOI":"10.13039\/501100003397","name":"Huazhong University of Science and Technology","doi-asserted-by":"crossref","award":["2016YXMS073"],"award-info":[{"award-number":["2016YXMS073"]}],"id":[{"id":"10.13039\/501100003397","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["U1401258 and 61572221"],"award-info":[{"award-number":["U1401258 and 61572221"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2017,4,30]]},"abstract":"<jats:p>Stable model semantics had been recently generalized to non-Herbrand structures by several works, which provides a unified framework and solid logical foundations for answer set programming. This article focuses on the expressiveness of normal and disjunctive logic programs under general stable model semantics. A translation from disjunctive logic programs to normal logic programs is proposed for infinite structures. Over finite structures, some disjunctive logic programs are proved to be intranslatable to normal logic programs if the arities of auxiliary predicates and functions are bounded in a certain way. The equivalence of the expressiveness of normal logic programs and disjunctive logic programs over arbitrary structures is also shown to coincide with that over finite structures and coincide with whether the complexity class NP is closed under complement. Moreover, to obtain a more explicit picture of the expressiveness, some intertranslatability results between logic program classes, and fragments of second-order logic are established.<\/jats:p>","DOI":"10.1145\/3039244","type":"journal-article","created":{"date-parts":[[2017,5,8]],"date-time":"2017-05-08T12:26:59Z","timestamp":1494246419000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Expressiveness of Logic Programs under the General Stable Model Semantics"],"prefix":"10.1145","volume":"18","author":[{"given":"Heng","family":"Zhang","sequence":"first","affiliation":[{"name":"Tianjin University, Tianjin, China"}]},{"given":"Yan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Western Sydney University, NSW, Australia"}]}],"member":"320","published-online":{"date-parts":[[2017,5,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80071-6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2011.11.001"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530761"},{"volume-title":"Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning. 298--307","author":"Chen Y.","key":"e_1_2_1_5_1","unstructured":"Y. Chen , F. Lin , Y. Wang , and M. Zhang . 2006. First-order loop formulas for normal logic programs . In Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning. 298--307 . Y. Chen, F. Lin, Y. Wang, and M. Zhang. 2006. First-order loop formulas for normal logic programs. In Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning. 298--307."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.12.001"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502810"},{"key":"e_1_2_1_8_1","volume-title":"Research Report 20--2004, LIF","author":"Durand A.","year":"2004","unstructured":"A. Durand , E. Grandjean , and F. Olive . 2004 . New results on arity vs. number of variables. Research Report 20--2004, LIF , Marseille , France (2004). A. Durand, E. Grandjean, and F. Olive. 2004. New results on arity vs. number of variables. Research Report 20--2004, LIF, Marseille, France (2004)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/8.2.189"},{"key":"e_1_2_1_10_1","unstructured":"H.-D. Ebbinghaus and J. Flum. 1999. Finite Model Theory (2nd ed.). Springer-Verlag New York.  H.-D. Ebbinghaus and J. Flum. 1999. Finite Model Theory (2nd ed.). Springer-Verlag New York."},{"key":"e_1_2_1_11_1","first-page":"1","article-title":"Model-based recasting in answer-set programming","volume":"23","author":"Eiter Thomas","year":"2013","unstructured":"Thomas Eiter , Michael Fink , J\u00f6rg P\u00fchrer , Hans Tompits , and Stefan Woltran . 2013 . Model-based recasting in answer-set programming . J. Appl. Non-Class. Logics 23 , 1 -- 2 (2013), 75--104. Thomas Eiter, Michael Fink, J\u00f6rg P\u00fchrer, Hans Tompits, and Stefan Woltran. 2013. Model-based recasting in answer-set programming. J. Appl. Non-Class. Logics 23, 1--2 (2013), 75--104.","journal-title":"J. Appl. Non-Class. Logics"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 9th International Conference on Principles of Knowledge Representation and Reasoning. 447--458","author":"Eiter Thomas","year":"2004","unstructured":"Thomas Eiter , Michael Fink , Hans Tompits , and Stefan Woltran . 2004 . On eliminating disjunctions in stable logic programming . In Proceedings of the 9th International Conference on Principles of Knowledge Representation and Reasoning. 447--458 . Thomas Eiter, Michael Fink, Hans Tompits, and Stefan Woltran. 2004. On eliminating disjunctions in stable logic programming. In Proceedings of the 9th International Conference on Principles of Knowledge Representation and Reasoning. 447--458."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(97)00027-7"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(95)00033-X"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261126"},{"key":"e_1_2_1_16_1","first-page":"43","article-title":"Generalized first-order spectra and polynomial-time recognizable sets","volume":"7","author":"Fagin R.","year":"1974","unstructured":"R. Fagin . 1974 . Generalized first-order spectra and polynomial-time recognizable sets . In Complexity of Computation (SIAM-AMS Proceedings) , Vol. 7. 43 -- 73 . R. Fagin. 1974. Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation (SIAM-AMS Proceedings), Vol. 7. 43--73.","journal-title":"Complexity of Computation (SIAM-AMS Proceedings)"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.04.011"},{"volume-title":"Proceedings of the 21st International Joint Conference on Artificial Intelligence. 797--803","author":"Ferraris P.","key":"e_1_2_1_18_1","unstructured":"P. Ferraris , J. Lee , V. Lifschitz , and R. Palla . 2009. Symmetric splitting in the general theory of stable models . In Proceedings of the 21st International Joint Conference on Artificial Intelligence. 797--803 . P. Ferraris, J. Lee, V. Lifschitz, and R. Palla. 2009. Symmetric splitting in the general theory of stable models. In Proceedings of the 21st International Joint Conference on Artificial Intelligence. 797--803."},{"volume-title":"Proceedings of the 5th International Conference and Symposium on Logic Programming. 1070--1080","author":"Gelfond M.","key":"e_1_2_1_19_1","unstructured":"M. Gelfond and V. Lifschitz . 1988. The stable model semantics for logic programming . In Proceedings of the 5th International Conference and Symposium on Logic Programming. 1070--1080 . M. Gelfond and V. Lifschitz. 1988. The stable model semantics for logic programming. In Proceedings of the 5th International Conference and Symposium on Logic Programming. 1070--1080."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01699468"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.3166\/jancl.16.35-86"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2208436.2208441"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90019-6"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 7th International Conference on Logic Programming and Nonmonotonic Reasoning. 346--350","author":"Lierler Yuliya","year":"2004","unstructured":"Yuliya Lierler and Marco Maratea . 2004 . Cmodels-2: SAT-based answer set solver enhanced to non-tight programs . In Proceedings of the 7th International Conference on Logic Programming and Nonmonotonic Reasoning. 346--350 . Yuliya Lierler and Marco Maratea. 2004. Cmodels-2: SAT-based answer set solver enhanced to non-tight programs. In Proceedings of the 7th International Conference on Logic Programming and Nonmonotonic Reasoning. 346--350."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2004.04.004"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.04.001"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"J. Lobo J. Minker and A. Rajasekar. 1992. Foundations of Disjunctive Logic Programming. The MIT Press Cambridge.   J. Lobo J. Minker and A. Rajasekar. 1992. Foundations of Disjunctive Logic Programming. The MIT Press Cambridge.","DOI":"10.1016\/B978-0-12-450010-5.50022-0"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11225-005-8473-8"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1053"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"e_1_2_1_32_1","unstructured":"Heng Zhang and Yan Zhang. 2013a. Disjunctive logic programs versus normal logic programs. CoRR abs\/1304.0620 http:\/\/arxiv.org\/abs\/1304.0620.  Heng Zhang and Yan Zhang. 2013a. Disjunctive logic programs versus normal logic programs. CoRR abs\/1304.0620 http:\/\/arxiv.org\/abs\/1304.0620."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 23rd International Joint Conference on Artificial Intelligence. 1198--1204","author":"Zhang Heng","year":"2013","unstructured":"Heng Zhang and Yan Zhang . 2013 b. First-order expressibility and boundedness of disjunctive logic programs . In Proceedings of the 23rd International Joint Conference on Artificial Intelligence. 1198--1204 . Heng Zhang and Yan Zhang. 2013b. First-order expressibility and boundedness of disjunctive logic programs. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence. 1198--1204."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2283516.2283585"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 24th International Joint Conference on Artificial Intelligence. 3292--3298","author":"Zhou Yi","year":"2015","unstructured":"Yi Zhou . 2015 . First-order disjunctive logic programming vs normal logic programming . In Proceedings of the 24th International Joint Conference on Artificial Intelligence. 3292--3298 . Yi Zhou. 2015. First-order disjunctive logic programming vs normal logic programming. In Proceedings of the 24th International Joint Conference on Artificial Intelligence. 3292--3298."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3039244","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3039244","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:30Z","timestamp":1750217790000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3039244"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,30]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,4,30]]}},"alternative-id":["10.1145\/3039244"],"URL":"https:\/\/doi.org\/10.1145\/3039244","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2017,4,30]]},"assertion":[{"value":"2015-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}