Sat, 16 Apr 1994 05:02:46 GMT

Related articles |
---|

Combinatorics of algebraic expressions szabo@netcom.com (1994-04-16) |

Re: Combinatorics of algebraic expressions Philippe.Flajolet@inria.fr (1994-04-20) |

Newsgroups: | sci.math,comp.theory,comp.compilers |

From: | szabo@netcom.com (Nick Szabo) |

Keywords: | theory, question |

Organization: | NETCOM On-line Communication Services (408 241-9760 guest) |

Date: | Sat, 16 Apr 1994 05:02:46 GMT |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.