Efficient Inclusion Checking for Deterministic Tree Automata and DTDs
Résumé
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 .
Fichier principal
lata08_paper.pdf (494.01 Ko)
Télécharger le fichier
lata08_talk.pdf (314.64 Ko)
Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Autre