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

https://hal.inria.fr/inria-00366082
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

File

ic09.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

155

Files downloads

163