Skip to Main content Skip to Navigation
Journal articles

Efficient Inclusion Checking for Deterministic Tree Automata and XML Schemas

Jérôme Champavère 1, 2, * Rémi Gilleron 1, 2 Aurélien Lemay 1, 2 Joachim Niehren 1, 2
* Corresponding author
2 MOSTRARE - Modeling Tree Structures, Machine Learning, and Information Extraction
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [30 references]  Display  Hide  Download
Contributor : Joachim Niehren <>
Submitted on : Saturday, October 10, 2009 - 10:15:56 PM
Last modification on : Tuesday, April 28, 2020 - 11:52:03 AM
Long-term archiving on: : Saturday, November 26, 2016 - 2:10:51 PM


Files produced by the author(s)




Jérôme Champavère, Rémi Gilleron, Aurélien Lemay, Joachim Niehren. Efficient Inclusion Checking for Deterministic Tree Automata and XML Schemas. Information and Computation, Elsevier, 2009, 207 (11), pp.1181-1208. ⟨10.1016/j.ic.2009.03.003⟩. ⟨inria-00366082v3⟩



Record views


Files downloads