Efficient inclusion checking for deterministic tree automata and XML Schemas

We present algorithms for testing language inclusion L(A)⊆L(B) between tree automata in time O(|A|·|B|) where B is deterministic (bottom-up or top-down). We extend our algorithms for testing inclusion of automata for unranked trees A in deterministic DTDs or deterministic EDTDs with restrained competition D in time O(|A|·|Σ|·|D|). Previous algorithms were less efficient or less general.