Skip to main content
Article
Head-Elementary-Set-Free Logic Programs
Computer Science Faculty Proceedings & Presentations
  • Martin Gebser, Institut fur Informatik
  • Joohyung Lee, Arizona State University
  • Yuliya Lierler, University of Nebraska at Omaha
Document Type
Conference Proceeding
Publication Date
1-1-2007
Disciplines
Abstract

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-Eiiyahu and Dechter. that can still be turned into nondisjunct:ive 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.

Comments

9th International Conference on Logic Programming and Nonmonotonic Reasoning

Citation Information
Martin Gebser, Joohyung Lee and Yuliya Lierler. "Head-Elementary-Set-Free Logic Programs" (2007)
Available at: http://works.bepress.com/yuliya_lierler/7/