Summary: Normal Forms in Function Fields
We consider function fields of functions of one variable
augmented by the binary operation of composition of
functions. It is shown that the straightforward axiom-
atization of this concept allows the introduction of a
normal form for expressions denoting elements in such
fields. While the description of this normal form seems
relatively intuitive, it is surprisingly difficult to prove
this fact. We present an algorithm for the normaliza-
tion of expressions, formulated in the symbolic com-
puter algebra language mathematica. This allows us to
effectively decide compositional identities in such fields.
Examples are given.
One of the fundamental questions in symbolic compu-
tation is to find normal forms for expressions where
certain identities are considered to be valid for these