{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T09:33:43Z","timestamp":1778751223188,"version":"3.51.4"},"reference-count":26,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2014,9,5]],"date-time":"2014-09-05T00:00:00Z","timestamp":1409875200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2015,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper proposes a model, the linear model, for randomly generating logic programs with low density of rules and investigates statistical properties of such random logic programs. It is mathematically shown that the average number of answer sets for a random program converges to a constant when the number of atoms approaches infinity. Several experimental results are also reported, which justify the suitability of the linear model. It is also experimentally shown that, under this model, the size distribution of answer sets for random programs tends to a normal distribution when the number of atoms is sufficiently large.<\/jats:p>","DOI":"10.1017\/s1471068414000611","type":"journal-article","created":{"date-parts":[[2014,9,5]],"date-time":"2014-09-05T10:01:38Z","timestamp":1409911298000},"page":"818-853","source":"Crossref","is-referenced-by-count":4,"title":["Random logic programs: Linear model"],"prefix":"10.1017","volume":"15","author":[{"given":"KEWEN","family":"WANG","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"LIAN","family":"WEN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KEDIAN","family":"MU","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,9,5]]},"reference":[{"key":"S1471068414000611_ref26","doi-asserted-by":"crossref","unstructured":"Zhao Y. and Lin F. 2003. Answer set programming phase transition: A study on randomly generated programs. In Proceedings of the 19th International Conference on Logic Programming (ICLP-03), 239\u2013253.","DOI":"10.1007\/978-3-540-24599-5_17"},{"key":"S1471068414000611_ref24","unstructured":"Syrj\u00e4nen T. and Niemel\u00e4 I. 2001. The smodels system. In Proceedings of the 6th International ConferenceLogic Logic Programming and Nonmonotonic Reasoning (LPNMR-01), 434\u2013438."},{"key":"S1471068414000611_ref21","doi-asserted-by":"crossref","unstructured":"Namasivayam G. and Truszczynski M. 2009. Simple random logic programs. In Proceedings of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR-09), 223\u2013235.","DOI":"10.1007\/978-3-642-04238-6_20"},{"key":"S1471068414000611_ref20","doi-asserted-by":"crossref","unstructured":"Namasivayam G. 2009. Study of random logic programs. In Proceedings of the 25th International Conference on Logic Programming (ICLP-09), 555\u2013556.","DOI":"10.1007\/978-3-642-02846-5_61"},{"key":"S1471068414000611_ref19","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G"},{"key":"S1471068414000611_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02906-0"},{"key":"S1471068414000611_ref16","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116836"},{"key":"S1471068414000611_ref18","unstructured":"Mitchell D. , Selman B. and Levesque H. 1992. Hard and easy distributions of sat problems. In Proceedings of the 10th National Conference on Artificial Intelligence (AAAI-92), 459\u2013465."},{"key":"S1471068414000611_ref5","first-page":"167","article-title":"Semantics of disjunctive logic programs based on partial evaluation","volume":"38","author":"Brass","year":"1999","journal-title":"Journal of Logic Programming"},{"key":"S1471068414000611_ref9","unstructured":"Gelfond M. and Lifschitz V. 1990. The stable model semantics for logic programming. In Proceedings of the 5th International Conference on Logic Programming (ICLP-88), 1070\u20131080."},{"key":"S1471068414000611_ref25","doi-asserted-by":"publisher","DOI":"10.1145\/1055686.1055690"},{"key":"S1471068414000611_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068408003645"},{"key":"S1471068414000611_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24750-0"},{"key":"S1471068414000611_ref14","doi-asserted-by":"publisher","DOI":"10.1145\/1149114.1149117"},{"key":"S1471068414000611_ref13","doi-asserted-by":"publisher","DOI":"10.3166\/jancl.16.35-86"},{"key":"S1471068414000611_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/S147106840300173X"},{"key":"S1471068414000611_ref1","doi-asserted-by":"crossref","unstructured":"Achlioptas D. , Kirousis L. , Kranakis E. , Krizanc D. , Molloy M. and Stamatiou Y. 1997. Random constraint satisfaction: A more accurate picture. In Proceedings of the 3rd International Conference on Principles and Practice of Constraint Programming (CP-97), 107\u2013120.","DOI":"10.1007\/BFb0017433"},{"key":"S1471068414000611_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(87)90033-6"},{"key":"S1471068414000611_ref22","unstructured":"Schlipf J. , Truszczynski M. and Wong D. 2005. On the distribution of programs with stable models. In Dagstuhl Seminar 05171 Abstracts Collection - Nonmonotonic Reasoning, Answer Set Prorgamming and Constraints."},{"key":"S1471068414000611_ref2","doi-asserted-by":"publisher","DOI":"10.1038\/nature03602"},{"key":"S1471068414000611_ref6","unstructured":"Cheeseman P. , Kanefsky B. and Taylor W. M. 1991. Where the really hard problems are. In Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI-91), 331\u2013340."},{"key":"S1471068414000611_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60085-2_10"},{"key":"S1471068414000611_ref7","doi-asserted-by":"crossref","unstructured":"Gebser M. , Kaufmann B. and Schaub T. 2009. The conflict-driven answer set solver clasp: Progress report. In Proceedings of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR-09), 509\u2013514.","DOI":"10.1007\/978-3-642-04238-6_50"},{"key":"S1471068414000611_ref8","unstructured":"Gelfond M. and Lifschitz V. 1988. Logic programs with classical negation. In Proceedings of the 7th International Conference on Logic Programming (ICLP-90), 579\u2013597."},{"key":"S1471068414000611_ref10","unstructured":"Gent I. and Walsh T. 1994. The sat phase transition. In Proceedings of the Eleventh European Conference on Artificial Intelligence (ECAI-94), 105\u2013109."},{"key":"S1471068414000611_ref11","doi-asserted-by":"crossref","unstructured":"Huang G. , Jia X., C. and You J. 2002. Two-literal logic programs and satisfiability representation of stable models: A comparison. In Proceedings 15th Canadian Conference on Artificial Intelligence, 119\u2013131.","DOI":"10.1007\/3-540-47922-8_11"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068414000611","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,19]],"date-time":"2019-04-19T22:23:18Z","timestamp":1555712598000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068414000611\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,5]]},"references-count":26,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["S1471068414000611"],"URL":"https:\/\/doi.org\/10.1017\/s1471068414000611","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,5]]}}}