Efficient Inclusion Checking for Deterministic Tree Automata and DTDs - Archive ouverte HAL Access content directly
Conference Papers Year : 2008

Efficient Inclusion Checking for Deterministic Tree Automata and DTDs

(1, 2) , (1, 2) , (1, 2) , (1, 2)
1
2

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 .
Fichier principal
Vignette du fichier
lata08_paper.pdf (494.01 Ko) Télécharger le fichier
Vignette du fichier
lata08_talk.pdf (314.64 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Other

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⟩
191 View
338 Download

Share

Gmail Facebook Twitter LinkedIn More