# Heuristics for space-efficient storing of Unordered Finite Sets in a DFA

I've got an algorithm I'm working on that generates, stores, and iterates through a large number of finite sets. I'm finding that memory is a bottleneck long before time is.

The finite sets are subsets of the vertices $V$ in my graph, so each finite set is small, there's just a lot of them.

In an effort to save space, I've started representing the finite sets as binary words of length $|V|$, with a 0 indicating the element is not in the set, a 1 indicating that it is. I'm storing the collection of these words as an acyclic deterministic automaton (also known as DAWG, directed acyclic word graph).

However, this requires a fixed ordering of the potential elements, which is fine, but arbitrary. If a different ordering were more likely to produce a smaller output set, I'd be happy to use it.

I'm wondering:

• Is there a known, efficient algorithm for finding the permutation which gives the smallest DFA representing a set of finite sets?
• If not, has any research been done on heuristics for orderings which have been shown to often produce smaller DFAs?

It sounds like you are describing a binary decision diagram, also known as a BDD. BDD's have been studied extensively in the literature, so you might take a look at the literature.

In particular, the question of finding the best permutation is known as the "variable ordering" problem for BDDs. Finding the optimal variable ordering is NP-hard. There are some heuristics, but they don't always work. See https://en.wikipedia.org/wiki/Binary_decision_diagram#Variable_ordering. Probably the easiest approach is to use an existing BDD library (the standard ones will typically incorporate some variable ordering heuristics).

You might also be interested in ZDDs.

• Very interesting! Would it be safe to say that a Trie is a Binary Decision Tree where all paths leading to 0 are pruned, and a DAWG is a BDD where paths leading to 0 are pruned? Both of these assuming that our alphabet is binary? (I can see that with a larger alphabet, a Trie will be different from a BDT ) – jmite Oct 8 '15 at 20:04
• @jmite, that sounds entirely believable to me, but I'm not an expert and I haven't thought about it too carefully, so don't trust anything I have to say about it. Yeah, I think BDDs assume the alphabet is binary. – D.W. Oct 8 '15 at 20:15
• Thus the B of BDD! – jmite Oct 8 '15 at 20:21