# On Elementary Loops Of Logic Programs

Martin Gebser Institut f¨ur Informatik Universit¨at Potsdam, Germany
(**e-mail:** gebser@cs.uni-potsdam.de)
Joohyung Lee School of Computing, Informatics and Decision Systems Engineering Arizona State University, USA
(**e-mail:** joolee@asu.edu)
Yuliya Lierler Department of Computer Science University of Kentucky, USA
(**e-mail:** yuliya@cs.uky.edu)
submitted 23 May 2010; revised ; accepted 18 August 2010 Note: To appear in *Theory and Practice of Logic Programming (TPLP)*

## Abstract

Using the notion of an elementary loop, Gebser and Schaub refined the theorem on loop formulas due to Lin and Zhao by considering loop formulas of elementary loops only. In this article, we reformulate their definition of an elementary loop, extend it to disjunctive programs, and study several properties of elementary loops, including how maximal elementary loops are related to minimal unfounded sets. The results provide useful insights into the stable model semantics in terms of elementary loops. For a nondisjunctive program, using a graph-theoretic characterization of an elementary loop, we show that the problem of recognizing an elementary loop is tractable. On the other hand, we show that the corresponding problem is coNP-complete for a disjunctive program. Based on the notion of an elementary loop, we present the class of Head-Elementary-loop-Free (HEF) programs, which strictly generalizes the class of Head-Cycle-Free (HCF) programs due to Ben-Eliyahu and Dechter. Like an HCF program, an HEF program can be turned into an equivalent nondisjunctive program in polynomial time by shifting head atoms into the body.

KEYWORDS: stable model semantics, loop formulas, unfounded sets

## 1 Introduction

The theorem on loop formulas due to Lin and Zhao (2004) has contributed to understanding the relationship between the stable model semantics and classical logic. Unlike other translations that modify the vocabulary of a logic program
(Ben-Eliyahu and Dechter 1994; Lin and Zhao 2003; Janhunen 2006), the original arXiv:1012.5847v2 [cs.AI] 2 Jan 2011