In Chapter 3 we described the tree structure of an expression. An expression also has a semantic structure that is related to its mathematical properties. For example, the expression 3 x ²+4 x+5/2 can be viewed both as an expression tree and semantically as a polynomial in x with degree 2 that has rational number coefficients.

In this chapter, we describe the polynomial structure and rational ex pression structure of an algebraic expression. For polynomials, we give three definitions of increasing generality: first for single variable polynomials (Section 6.1); next for multivariate polynomials (Section 6.1); and finally for general polynomial expressions (Sections 6.2 and 6.3). The definitions are more involved than those found in mathematics textbooks, since they focus on computational concerns as well as the mathematical concept of a polynomial. Along with these definitions, we give MPL procedures that determine the polynomial structure of an expression. In Section 6.4, we use these structural concepts to describe the goals of two transformations, coefficient collection and algebraic expansion, and give MPL algorithms for these operations. Finally, in Section 6.5 we describe the rational expression structure of an algebraic expression and give an algorithm that transforms an expression to a particular rational form.

Although operators that determine the structure of polynomials and rational expressions are available in most computer algebra languages, their capacity varies from system to system. The concepts in this chapter provide a framework to analyze and compare how these concepts are implemented in...