1
$\begingroup$

A DAWG is a specialized form of a Directed Acyclic Graph. Admittedly, not terribly specialized. I was wondering if DAWGs built from proper sets (unique, sorted) had any special properties? It seems to me that they ought to have a couple of interesting properties regarding dependencies between the "layers" but but I'm at a loss as to how to prove it either way. Anyone got a bit more knowledge regarding these bits of esoterica?

$\endgroup$
3
  • $\begingroup$ but what is a DAWG ? can you define it, or point to a definition ? $\endgroup$ Jan 14 '11 at 4:44
  • $\begingroup$ Wiki-link laid in. $\endgroup$ Jan 14 '11 at 4:45
  • 2
    $\begingroup$ A DAWG has precisely one vertex with in-degree 0. That's the only thing which is obviously special about it. $\endgroup$ Jan 14 '11 at 11:55
2
$\begingroup$

I could be missing something, but if you took an arbitrary DAG, assigned unique IDs to each vertex, and constructed all words formed by traversing monotone chains from top to bottom, then wouldn't the DAWG of that set be the original DAG ? If so, then a DAWG has no special structure.

Update: Peter Taylor's comment is the key difference. only one node with indegree 0 unlike a regular DAG.

$\endgroup$
2
  • 1
    $\begingroup$ Very almost. You may need to add a root node if you have more than one node with in-degree 0. $\endgroup$ Jan 14 '11 at 19:51
  • $\begingroup$ correct. I forgot about the single node issue. $\endgroup$ Jan 14 '11 at 23:09
0
$\begingroup$

DAWGs are most probably posets and close relatives of Finite Automata.

So special properties of posets and FA should apply to DAWGs too.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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