Combinatorics of algebraic expressions

I'd like to derive complexity measures for expressions in various
canonical algebras. Specifically, given a a set of variables and an
operator *, I'd like to derive the number of syntactically unique
expressions, and conversely, the probability of randomly generating a
specific expression. Assuming the variables are assigned i.i.d. randomly
from the algebra's carrier set, I'd also like to derive the probability of
generating synonyms (syntactically different expressions that evaluate the
the same value).


At the very least I'd like measures based on the size of the expression
(either the number of operators or number of variables used, or both).
Ideally I'd like general complexity measures based on the size of the
expression, the size of the variable set, the (size of the?) carrier set,
and the properties of the algebra. For example, if * is associative this
increases the number of synonyms (and thus the number of possible values),
as does commutativity, and an associative and commutative operator would
increase synonyms even more. Presumably it doesn't matter if the carrier
set is infinite since the number of variables are finite, but a small
carrier set (eg boolean algebras) greatly increases the number of synonyms.


I'd greatly appreciated pointers to references where folks have worked out
several of these kinds of problems, or better yet general theorems. The
only example I've found so far is Sahni's textbooks, _Concepts in Discrete
Mathematics_, pg. 429, which computes the number of ways to multiply n
matrices M1*M2*...*Mn (ie the number of synonyms for this expression).
Matrices with multiplication forms a semigroup, associative but not
commutative, so that grouping doesn't matter, but order does. For example
for M=5 we have 8 different ways to evaluate the expression:


(((M1*M2)*M3)*M4)*M5
((M1*M2)*(M3*M4))*M5
(M1*(M2*M3))*(M4*M5)
...


Clearly, m[1]=m[2]=1. When n>1, the last product product to
be evaluated takes the form M1,k * Mk+1,n where
M1,k = M1*...*Mk, and Mk+1,n = Mk+1 * ... *Mn, 1<=k<n.
There are m[k] ways to compute M1,k and m[n-k] ways
to compute Mk+1,n. This gives us the recurrence


m[n] = 1 if n=1;
sum(1<=k<n) m[k]*m[n-k] if n>1


This turns out to equal b[n-1], the number of possible binary trees with
n-1 nodes. The recurrence solves to


m[n] = (1/n)(2n-2 choose n-1)


I conjecture that this gives what I've dubbed a "synonym complexity", the
proportion of expressions that are synonyms, for any expression formed by
the rules of any noncommutative semigroup using n variables in fixed
order. I'd like to generalize this to variables drawn i.i.d. from the
variable set.


I'd like to solicit comments or pointers to general work along these lines
-- how to derive expression complexity measures from algebraic properties.
If there isn't any such general work, what math or computer science
publications would be interested in a paper on the topic?
--
Nick Szabo szabo@netcom.com
--

Return to the comp.compilers page.
Search the comp.compilers archives again.