Efficient Inclusion Checking for Deterministic Tree Automata and DTDs

We present a new algorithm for testing language inclusion L(A) < L(B) between tree automata in time O(|A|*|B|) where B is deterministic. We extend this algorithm for testing inclusion between automata for unranked trees A and deterministic DTDs D in time O(|A|*|\Sigma|*|D|). No previous algorithms with these complexities exist. Extended version available at http://www.grappa.univ-lille3.fr/~champavere/Recherche/publications/CGLN08EIC.extended.pdf

Mots clés

tree automata language inclusion algorithmic complexity XML DTD

Domaines

Algorithme et structure de données [cs.DS] Web Informatique et langage [cs.CL]

Fichier principal

0.pdf (527.28 Ko)

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

Joachim Niehren : Connectez-vous pour contacter le contributeur

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

Soumis le : vendredi 14 mars 2008-17:59:08

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

Archivage à long terme le : vendredi 25 novembre 2016-21:37:06

Dates et versions

inria-00192329 , version 1 (19-02-2008)

inria-00192329 , version 2 (14-03-2008)

inria-00192329 , version 3 (11-06-2008)

inria-00192329 , version 4 (16-02-2009)

inria-00192329 , version 5 (04-03-2009)

inria-00192329 , version 6 (05-03-2009)

Identifiants

HAL Id : inria-00192329 , version 2

Citer

Jérôme Champavère, Rémi Gilleron, Aurélien Lemay, Joachim Niehren. Efficient Inclusion Checking for Deterministic Tree Automata and DTDs. 2nd International Conference on Language and Automata Theory and Applications, Mar 2008, Tarragona, Spain. ⟨inria-00192329v2⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

LIFL

213 Consultations

370 Téléchargements