Head-elementary-set-free logic programs

Martin Gebser, Joohyung Lee, Yuliya Lierler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations


The recently proposed notion of an elementary set yielded a refinement of the theorem on loop formulas, telling us that the stable models of a disjunctive logic program can be characterized by the loop formulas of its elementary sets. Based on the notion of an elementary set, we propose the notion of head-elementary-set-free (HEF) programs, a more general class of disjunctive programs than head-cycle-free (HCF) programs proposed by Ben-Eliyahu and Dechter, that can still be turned into nondisjunctive programs in polynomial time and space by "shifting" the head atoms into the body. We show several properties of HEF programs that generalize earlier results on HCF programs. Given an HEF program, we provide an algorithm for finding an elementary set whose loop formula is not satisfied, which has a potential for improving stable model computation by answer set solvers.

Original languageEnglish (US)
Title of host publicationLogic Programming and Nonmonotonic Reasoning - 9th International Conference, LPNMR 2007, Proceedings
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783540721994
StatePublished - 2007
Event9th International Conference on Logic Programming and Nonmonotomic Reasoning, LPNMR 2007 - Tempe, AZ, United States
Duration: May 15 2007May 17 2007

Publication series

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


Other9th International Conference on Logic Programming and Nonmonotomic Reasoning, LPNMR 2007
Country/TerritoryUnited States
CityTempe, AZ

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Head-elementary-set-free logic programs'. Together they form a unique fingerprint.

Cite this