Then M contains the transitions − − → s (this assigns the initial state of A to the top-most edge of the spine), − − → {ξ } for all ξ ∈ Ξ, q ∈ Q, and ξ, q, ξ ∈ τ (this "reads" q on an incoming edge in state ξ, assigning the resulting state ξ to the next edge on the spine), − − → {s } for all final states ξ of A (this allows A to "cross" the middle of the spine and continue to work on the outgoing edges) and, similarly to the preceding items, − − → {ξ , q} for all ξ ∈ Ξ , q ∈ Q, and ξ, q, ξ ∈ τ (similarly to the second item, but "reading" q on an outgoing edge) and .
we can extend three results from non-extended DAG automata to extended ones: The emptiness and finiteness problems are decidable and the path languages are regular.