Skip to Main content Skip to Navigation
Other publications

Efficient Inclusion Checking for Deterministic Tree Automata and DTDs

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

https://hal.inria.fr/inria-00192329
Contributor : Joachim Niehren Connect in order to contact the contributor
Submitted on : Tuesday, February 19, 2008 - 3:43:02 PM
Last modification on : Tuesday, April 28, 2020 - 11:52:08 AM
Long-term archiving on: : Thursday, September 27, 2012 - 10:25:23 AM

File

0.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00192329, version 1

Collections

Citation

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⟩

Share

Metrics

Les métriques sont temporairement indisponibles