Normal forms in function fields

ABSTRACT

We consider function fields of functions of one variable augmented by the binary operation of composition of functions. It is shown that the straightforward axiomatization 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 normalization of expressions, formulated in the symbolic computer algebra language mathematica. This allows us to effectively decide compositional identities in such fields. Examples are given.

REFERENCES

• 1: Aberer, K.: "Normal Forms in Combinatory Differential Fields". ETtf-Report No. 89.t)I, (1989).
• 2: Davenport, J.H., Siret, Y. and Tournier, E.' "Computer Alsebra'. Academic Press, 17. Y., (1988).
• 3: E. Engeler, Combinatory differential fields, Theoretical Computer Science, v.72 n.2-3, p.119-131, May 23, 1990 [doi>10.1016/0304-3975(90)90031-C]
• 4: Keith O. Geddes , Stephen R. Czapor , George Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, Norwell, MA, 1992
• 5: Le Chenade~, P.: "Canonical Forms in Finitely Presented Algebras", Research Notes in Theoretical Computer Science, Pitman, (1986)
• 6: Meager, K.: "Function Algebra and Propositional Calculus". Self-Organizing Systems, Spartan Books, (I 962), p. 525ff.
• 7: Wolfram, S.: "Mathematica'. Addison-Wesley Publishing Company, (1988).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Simplification of expressions

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Languages