  Describing complex objects by elementary ones is a common strategy in
mathematics and science in general. In their seminal 1965 paper, Kenneth Krohn
and John Rhodes showed that every finite deterministic automaton can be
represented (or "emulated") by a cascade product of very simple automata. This
led to an elegant algebraic theory of automata based on finite semigroups
(Krohn-Rhodes Theory). Surprisingly, by relating logic programs and automata,
we can show in this paper that the Krohn-Rhodes Theory is applicable in Answer
Set Programming (ASP). More precisely, we recast the concept of a cascade
product to ASP, and prove that every program can be represented by a product of
very simple programs, the reset and standard programs. Roughly, this implies
that the reset and standard programs are the basic building blocks of ASP with
respect to the cascade product. In a broader sense, this paper is a first step
towards an algebraic theory of products and networks of nonmonotonic reasoning
systems based on Krohn-Rhodes Theory, aiming at important open issues in ASP
and AI in general.
