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

https://hal.inria.fr/inria-00366082
Contributor : Joachim Niehren <>
Submitted on : Saturday, October 10, 2009 - 10:15:56 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
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

463

Files downloads

322