Efficient Inclusion Checking for Deterministic Tree Automata and XML Schemas

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.

Mots clés

tree automata language inclusion algorithmic complexity XML schemas

Domaines

Algorithme et structure de données [cs.DS]

Fichier principal

ic09.pdf (856.72 Ko)

Origine : Fichiers produits par l'(les) auteur(s)

Joachim Niehren : Connectez-vous pour contacter le contributeur

https://inria.hal.science/inria-00366082

Soumis le : samedi 10 octobre 2009-22:15:56

Dernière modification le : vendredi 24 mars 2023-14:52:52

Archivage à long terme le : samedi 26 novembre 2016-14:10:51

Dates et versions

inria-00366082 , version 1 (05-03-2009)

inria-00366082 , version 2 (10-10-2009)

inria-00366082 , version 3 (10-10-2009)

Identifiants

HAL Id : inria-00366082 , version 3
DOI : 10.1016/j.ic.2009.03.003

Citer

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, 2009, 207 (11), pp.1181-1208. ⟨10.1016/j.ic.2009.03.003⟩. ⟨inria-00366082v3⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

UNIV-LILLE3 CNRS INRIA LIFL MOSTRARE INRIA2 ANR

160 Consultations

190 Téléchargements