TY - GEN

T1 - Simple random logic programs

AU - Namasivayam, Gayathri

AU - Truszczyński, Mirosław

PY - 2009

Y1 - 2009

N2 - We consider random logic programs with two-literal rules and study their properties. In particular, we obtain results on the probability that random "sparse" and "dense" programs with two-literal rules have answer sets. We study experimentally how hard it is to compute answer sets of such programs. For programs that are constraint-free and purely negative we show that the easy-hard-easy pattern emerges. We provide arguments to explain that behavior. We also show that the hardness of programs from the hard region grows quickly with the number of atoms. Our results point to the importance of purely negative constraint-free programs for the development of ASP solvers.

AB - We consider random logic programs with two-literal rules and study their properties. In particular, we obtain results on the probability that random "sparse" and "dense" programs with two-literal rules have answer sets. We study experimentally how hard it is to compute answer sets of such programs. For programs that are constraint-free and purely negative we show that the easy-hard-easy pattern emerges. We provide arguments to explain that behavior. We also show that the hardness of programs from the hard region grows quickly with the number of atoms. Our results point to the importance of purely negative constraint-free programs for the development of ASP solvers.

UR - http://www.scopus.com/inward/record.url?scp=70349850655&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70349850655&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-04238-6_20

DO - 10.1007/978-3-642-04238-6_20

M3 - Conference contribution

AN - SCOPUS:70349850655

SN - 3642042376

SN - 9783642042379

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 223

EP - 235

BT - Logic Programming and Nonmonotonic Reasoning - 10th International Conference, LPNMR 2009, Proceedings

Y2 - 14 September 2009 through 18 September 2009

ER -