Efficient Inclusion Checking for Deterministic Tree Automata and DTDs

Jérôme Champavère (1, 2) , Rémi Gilleron (1, 2) , Aurélien Lemay (1, 2) , Joachim Niehren (1, 2)

1 LIFL - Laboratoire d'Informatique Fondamentale de Lille
2 MOSTRARE - Modeling Tree Structures, Machine Learning, and Information Extraction

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 .

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]

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. pp.184-195. ⟨inria-00192329v6⟩