|
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.
|
