3
$\begingroup$

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?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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 ) $\endgroup$
    – jmite
    Oct 8, 2015 at 20:04
  • 1
    $\begingroup$ @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. $\endgroup$
    – D.W. ♦
    Oct 8, 2015 at 20:15
  • $\begingroup$ Thus the B of BDD! $\endgroup$
    – jmite
    Oct 8, 2015 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.