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
1 LIFL - Laboratoire d'Informatique Fondamentale de Lille
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.
Keywords : tree automata language inclusion algorithmic complexity XML schemas
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

LIFL | INRIA | UNIV-LILLE3 | MOSTRARE

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

463

Files downloads

322

Contact


archive-ouverte@inria.fr