  Non-monotonic reasoning is an essential part of human intelligence
prominently formalized in artificial intelligence research via answer set
programming. Describing complex objects as the composition of elementary ones
is a common strategy in computer science and science in general. This paper
contributes to the foundations of answer set programming and artificial
intelligence by introducing and studying the sequential composition of answer
set programs. Specifically, we show that the notion of composition gives rise
to a family of finite monoids and seminearrings, baptized {\em ASP monoids} and
{\em ASP seminearrings} in this paper. Particularly, we show that the
combination of composition and union yields the structure of a finite
idempotent seminearring. We also show that the restricted class of proper
Krom-Horn programs, which only contain rules with exactly one body atom, yields
a finite idempotent semiring. On the semantic side, we show that the van
Emden-Kowalski immediate consequence operator of a program can be represented
via composition, which allows us to compute the least model semantics of Horn
programs without any explicit reference to operators. As a result, we
characterize answer sets algebraically, which bridges the conceptual gap
between the syntax and semantics of an answer set program in a mathematically
satisfactory way, and which provides an algebraic characterization of strong
and uniform equivalence. Moreover, it gives rise to an algebraic meta-calculus
for answer set programs. In a broader sense, this paper is a further step
towards an algebra of rule-based logical theories and in the future we plan to
adapt and generalize the methods of this paper to wider classes of formalisms,
most importantly to first-order and disjunctive answer set programs and
extensions thereof.
