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 - https://www.scopus.com/pages/publications/70349850655
UR - https://www.scopus.com/pages/publications/70349850655#tab=citedBy
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
T2 - 10th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2009
Y2 - 14 September 2009 through 18 September 2009
ER -