Efficient Inclusion Checking for Deterministic Tree Automata and DTDs

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 .

Keywords

tree automata language inclusion algorithmic complexity XML DTD

Domains

Data Structures and Algorithms [cs.DS] Web Computation and Language [cs.CL]

Fichier principal

lata08_paper.pdf (494.01 Ko)

lata08_talk.pdf (314.64 Ko)

Origin : Files produced by the author(s)

Format : Other

Joachim Niehren : Connect in order to contact the contributor

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

Submitted on : Thursday, March 5, 2009-4:20:02 PM

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

Long-term archiving on: Saturday, November 26, 2016-6:28:16 AM

Dates and versions

inria-00192329 , version 1 (19-02-2008)

inria-00192329 , version 2 (14-03-2008)

inria-00192329 , version 3 (11-06-2008)

inria-00192329 , version 4 (16-02-2009)

inria-00192329 , version 5 (04-03-2009)

inria-00192329 , version 6 (05-03-2009)

Identifiers

HAL Id : inria-00192329 , version 6

Cite

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⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

UNIV-LILLE3 CNRS INRIA LIFL MOSTRARE INRIA2

213 View

370 Download