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?