Efficient Inclusion Checking for Deterministic Tree Automata and DTDs
Résumé
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
Origine : Fichiers produits par l'(les) auteur(s)