Because DAGs do not contain cycles, they must always have at least one root and one leaf, but they can have multiple roots and multiple leaves.
our results apply in different ways to single-rooted and multi-rooted DAG languages, so, given a label set Σ, we distinguish between the set of all connected DAGs with a single root, G 1 Σ ; and those with one or more roots, G * Σ .