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
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.
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

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〉

Partager

Métriques

Consultations de la notice

362

Téléchargements de fichiers

129