HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 metadata

Cited literature [30 references]  Display  Hide  Download

Contributor : Joachim Niehren Connect in order to contact the contributor
Submitted on : Saturday, October 10, 2009 - 10:15:56 PM
Last modification on : Wednesday, April 6, 2022 - 3:48:09 PM
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