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
* Auteur correspondant
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
Type de document :
Article dans une revue
Information and Computation, Elsevier, 2009, 207 (11), pp.1181-1208. 〈10.1016/j.ic.2009.03.003〉
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00366082
Contributeur : Joachim Niehren <>
Soumis le : samedi 10 octobre 2009 - 22:15:56
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : samedi 26 novembre 2016 - 14:10:51

Fichier

ic09.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

398

Téléchargements de fichiers

138

Contact


archive-ouverte@inria.fr