Skip to Main content Skip to Navigation
Conference papers

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 .
Complete list of metadata

https://hal.inria.fr/inria-00192329
Contributor : Joachim Niehren Connect in order to contact the contributor
Submitted on : Thursday, March 5, 2009 - 4:20:02 PM
Last modification on : Tuesday, April 28, 2020 - 11:52:08 AM
Long-term archiving on: : Saturday, November 26, 2016 - 6:28:16 AM

Identifiers

  • 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. 2nd International Conference on Language and Automata Theory and Applications, Mar 2008, Tarragona, Spain. pp.184-195. ⟨inria-00192329v6⟩

Share

Metrics

Record views

405

Files downloads

710