Simple random logic programs

Gayathri Namasivayam; Mirosław Truszczyński

doi:10.1007/978-3-642-04238-6_20

Simple random logic programs

Gayathri Namasivayam, Mirosław Truszczyński

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

8 Scopus citations

Abstract

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.

Original language	English
Title of host publication	Logic Programming and Nonmonotonic Reasoning - 10th International Conference, LPNMR 2009, Proceedings
Pages	223-235
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-642-04238-6_20
State	Published - 2009
Event	10th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2009 - Potsdam, Germany Duration: Sep 14 2009 → Sep 18 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5753 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2009
Country/Territory	Germany
City	Potsdam
Period	9/14/09 → 9/18/09

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Namasivayam, G., & Truszczyński, M. (2009). Simple random logic programs. In Logic Programming and Nonmonotonic Reasoning - 10th International Conference, LPNMR 2009, Proceedings (pp. 223-235). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5753 LNAI). https://doi.org/10.1007/978-3-642-04238-6_20

@inproceedings{7c3a84c8247940eaaca86c7c2e593d68,

title = "Simple random logic programs",

abstract = "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.",

author = "Gayathri Namasivayam and Miros{\l}aw Truszczy{\'n}ski",

year = "2009",

doi = "10.1007/978-3-642-04238-6_20",

language = "English",

isbn = "3642042376",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "223--235",

booktitle = "Logic Programming and Nonmonotonic Reasoning - 10th International Conference, LPNMR 2009, Proceedings",

note = "10th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2009 ; Conference date: 14-09-2009 Through 18-09-2009",

}

Namasivayam, G & Truszczyński, M 2009, Simple random logic programs. in Logic Programming and Nonmonotonic Reasoning - 10th International Conference, LPNMR 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5753 LNAI, pp. 223-235, 10th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2009, Potsdam, Germany, 9/14/09. https://doi.org/10.1007/978-3-642-04238-6_20

Simple random logic programs. / Namasivayam, Gayathri; Truszczyński, Mirosław.
Logic Programming and Nonmonotonic Reasoning - 10th International Conference, LPNMR 2009, Proceedings. 2009. p. 223-235 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5753 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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

T2 - 10th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2009

Y2 - 14 September 2009 through 18 September 2009

ER -

Simple random logic programs

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this