Efficient Inclusion Checking for Deterministic Tree Automata and

Abstract. We present a new algorithm for testing language inclusion L(A) ⊆ L(B) between tree automata in time O(|A | ∗ |B|) where B is deterministic. We extend this algorithm for testing inclusion between automata for unranked trees A and deterministic DTDsD in time O(|A|∗ |Σ | ∗ |D|). No previous algorithms with these complexities exist.