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)

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

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.

Mots clés: tree automata; language inclusion; algorithmic complexity; XML DTD

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

Jérôme Champavère, Rémi Gilleron, Aurélien Lemay, Joachim Niehren. Efficient Inclusion Checking for Deterministic Tree Automata and DTDs. 2008. ⟨inria-00192329v1⟩