|
Abstract. Let X be a subset of the free monoid {0, 1}*
which is the inverse image of the unit in a morphism which maps {0, 1}* into a finite group. For each integer n, let Xn consist of all the words in X of length n.
Identifying Xn with a
Boolean function on $n$ variables in the natural way, allows one to use an
ordered binary decision diagram (OBDD) to recognize it. Such a diagram can
be viewed as a finite deterministic automaton where the letters, instead of
being read from left to right, are being read in a predetermined order. For
a given Boolean function, the resulting size of the OBDD depends on the
choice of the order. We prove that for a wide variety of subsets X, under the uniform distribution
hypothesis over all orderings of $n$ elements, there exists a real α
> 1 such that with probability 1 when n tends to infinity, the size of the reduced OBDD computing Xn grows at least as fast
as αn.
|
