Normal forms for Answer Sets Programming
  Normal forms for logic programs under stable/answer set semantics are
introduced. We argue that these forms can simplify the study of program
properties, mainly consistency. The first normal form, called the {\em kernel}
of the program, is useful for studying existence and number of answer sets. A
kernel program is composed of the atoms which are undefined in the Well-founded
semantics, which are those that directly affect the existence of answer sets.
The body of rules is composed of negative literals only. Thus, the kernel form
tends to be significantly more compact than other formulations. Also, it is
possible to check consistency of kernel programs in terms of colorings of the
Extended Dependency Graph program representation which we previously developed.
The second normal form is called {\em 3-kernel.} A 3-kernel program is composed
of the atoms which are undefined in the Well-founded semantics. Rules in
3-kernel programs have at most two conditions, and each rule either belongs to
a cycle, or defines a connection between cycles. 3-kernel programs may have
positive conditions. The 3-kernel normal form is very useful for the static
analysis of program consistency, i.e., the syntactic characterization of
existence of answer sets. This result can be obtained thanks to a novel
graph-like representation of programs, called Cycle Graph which presented in
the companion article \cite{Cos04b}.
