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

Question

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?

Answer 1

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.