Efficient Inclusion Checking for Deterministic Tree Automata and XML Schemas

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.

Keywords

tree automata language inclusion algorithmic complexity XML schemas

Domains

Data Structures and Algorithms [cs.DS]

Fichier principal

ic09.pdf (856.72 Ko)

Origin : Files produced by the author(s)

Joachim Niehren : Connect in order to contact the contributor

https://inria.hal.science/inria-00366082

Submitted on : Saturday, October 10, 2009-10:15:56 PM

Last modification on : Friday, March 24, 2023-2:52:52 PM

Long-term archiving on: Saturday, November 26, 2016-2:10:51 PM

Dates and versions

inria-00366082 , version 1 (05-03-2009)

inria-00366082 , version 2 (10-10-2009)

inria-00366082 , version 3 (10-10-2009)

Identifiers

HAL Id : inria-00366082 , version 3
DOI : 10.1016/j.ic.2009.03.003

Cite

Jérôme Champavère, Rémi Gilleron, Aurélien Lemay, Joachim Niehren. Efficient Inclusion Checking for Deterministic Tree Automata and XML Schemas. Information and Computation, 2009, 207 (11), pp.1181-1208. ⟨10.1016/j.ic.2009.03.003⟩. ⟨inria-00366082v3⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

UNIV-LILLE3 CNRS INRIA LIFL MOSTRARE INRIA2 ANR

160 View

190 Download