1

Vietnam Journal of Mathematics 34:4(2006) 369-379

Recognizing Group Languages with OBDDs

Ch. Choffrut and Y. Haddad

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 $X_{n}$ consist of all the words in $X$ of length $n$. Identifying $X_{n}$ 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 $\alpha>1$ such that with probability $1$ when $n$ tends to infinity, the size of the reduced OBDD computing $X_{n}$ grows at least as fast as $\alpha^n$.

2000 Mathematics Subject Classification: 68R99, 94C10, 06E30.

Keywords: Boolean function, ordered binary decision diagram, finite group, finite deterministic automaton.