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?
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.
DAWGs are most probably posets and close relatives of Finite Automata.
So special properties of posets and FA should apply to DAWGs too.