| HAL-Inria | Publications, software ... of Inria's scientists |
Journal articles
Efficient Inclusion Checking for Deterministic Tree Automata and XML Schemas
Abstract : We present algorithms for testing language inclusion L(A) ⊆ L(B) between tree automata in time O(|A| |B|) where B is deterministic (bottom-up or top-down). We extend our algorithms for testing inclusion of automata for unranked trees A in deterministic DTDs or deterministic EDTDs with restrained competition D in time O(|A| |Σ| |D|). Previous algorithms were less efficient or less general.
Cited literature [30 references]
https://hal.inria.fr/inria-00366082
Contributor : Joachim Niehren Connect in order to contact the contributor
Submitted on : Saturday, October 10, 2009 - 10:15:56 PM
Last modification on : Wednesday, April 6, 2022 - 3:48:09 PM
Long-term archiving on: : Saturday, November 26, 2016 - 2:10:51 PM
Contributor : Joachim Niehren Connect in order to contact the contributor
Submitted on : Saturday, October 10, 2009 - 10:15:56 PM
Last modification on : Wednesday, April 6, 2022 - 3:48:09 PM
Long-term archiving on: : Saturday, November 26, 2016 - 2:10:51 PM
File
ic09.pdf
Files produced by the author(s)