Subject: binary tree formats in symbolic algebra ??
From: Henry Baker
Date: Fri, 22 Mar 2013 05:51:06 -0700
This is a general question about symbolic algebra systems, not a question about Maxima in particular.
Are there any algebra systems that utilize some sort of binary _tree_ format for symbolic expressions?
For example, a univariate polynomial might be encoded in a format like this:
C_i*x^2^i + D_i
and C_i, D_i are both analogous expressions, e.g., C_i = C_(i-1)*x^2^(i-1) + D_(i-1).
There is no change in the number of coefficients or the number of nodes, but instead of being stored in a linear list, the structure has more of a binary tree shape (nodes with zero coefficients are elided, so the tree often collapses a lot).
Granted, this representation is probably only useful for really large expressions, but I would imagine that symbolic algebra systems are working on some pretty large expressions these days.
If there are such systems, do you have an academic reference to a paper about such a system ?