Efficient Inclusion Checking for Deterministic Tree Automata and DTDs

Abstract : We present a new algorithm for testing language inclusion L(A) ⊆ L(B)L(A) 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| |Σ| |D|). No previous algorithms with these complexities exist.

A journal extension is available at http://hal.inria.fr/inria-00366082 .
Type de document :
Communication dans un congrès
Martin-Vide, Carlos and Otto, Friedrich and Fernau, Henning. 2nd International Conference on Language and Automata Theory and Applications, Mar 2008, Tarragona, Spain. Springer, 5196, pp.184-195, 2008, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00192329
Contributeur : Joachim Niehren <>
Soumis le : jeudi 5 mars 2009 - 16:20:02
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : samedi 26 novembre 2016 - 06:28:16

Identifiants

  • HAL Id : inria-00192329, version 6

Collections

Citation

Jérôme Champavère, Rémi Gilleron, Aurélien Lemay, Joachim Niehren. Efficient Inclusion Checking for Deterministic Tree Automata and DTDs. Martin-Vide, Carlos and Otto, Friedrich and Fernau, Henning. 2nd International Conference on Language and Automata Theory and Applications, Mar 2008, Tarragona, Spain. Springer, 5196, pp.184-195, 2008, Lecture Notes in Computer Science. 〈inria-00192329v6〉

Partager

Métriques

Consultations de la notice

295

Téléchargements de fichiers

233