<p>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. </p>

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

CC BY-SA 2.5
2011-01-14T19:51:03.963Z
Very almost. You may need to add a root node if you have more than one node with in-degree 0.
Peter Taylor
CC BY-SA 2.5
2011-01-14T23:09:12.847Z
correct. I forgot about the single node issue.
Suresh Venkat
CC BY-SA 2.5
2011-01-14T06:57:10.343Z
2011-01-14T23:09:54.393Z
2011-01-14T23:09:54.393Z
Suresh Venkat
<p>DAWGs are most probably <a href="http://en.wikipedia.org/wiki/Partially_ordered_set" rel="nofollow">posets</a> and close relatives of Finite Automata.</p>

<p>So special properties of posets and FA should apply to DAWGs too.</p>

CC BY-SA 2.5
2011-01-14T11:11:19.927Z
2011-01-14T11:11:19.927Z
Pratik Deoghare
<p>A <a href="http://en.wikipedia.org/wiki/DAWG" rel="nofollow">DAWG</a> 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?</p>

CC BY-SA 2.5
2011-01-14T04:44:20.987Z
but what *is* a DAWG ? can you define it, or point to a definition ?
Suresh Venkat
CC BY-SA 2.5
2011-01-14T04:45:36.083Z
Wiki-link laid in.
Jake Kurzer
CC BY-SA 2.5
2011-01-14T11:55:58.687Z
A DAWG has precisely one vertex with in-degree 0. That's the only thing which is obviously special about it.
Peter Taylor
<graph-theory><co.combinatorics><directed-acyclic-graph>
Special Properties Of DAWGs with Unique Elements
Jake Kurzer
# Special Properties Of DAWGs with Unique Elements

(Asked by: username_0 on 2011-01-14)

A [DAWG](http://en.wikipedia.org/wiki/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?

**Tags:** graph-theory, co.combinatorics, directed-acyclic-graph
> **Comments:**
> **username_1**: but what *is* a DAWG ? can you define it, or point to a definition ?  
> **username_0**: Wiki-link laid in.  
> **username_2**: A DAWG has precisely one vertex with in-degree 0. That's the only thing which is obviously special about it.  

---

## 2 answers

### Answer by username_1 on 2011-01-14. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_2**: Very almost. You may need to add a root node if you have more than one node with in-degree 0.  
> **username_1**: correct. I forgot about the single node issue.  

---

### Answer by username_3 on 2011-01-14. Score: 0

DAWGs are most probably [posets](http://en.wikipedia.org/wiki/Partially_ordered_set) and close relatives of Finite Automata.

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


---

