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.

Authors

• Jérôme Champavère
• Rémi Gilleron
• Aurélien Lemay
• Joachim Niehren

Keywords

• Tree automata
• Language inclusion
• Algorithmic complexity
• XML Shemas