🚀 go-pugleaf

Christine Delcroix <cde@info.fundp.ac.be> writes:

> Soient deux DTD, DTD1 et DTD2, telles que tous les documents conformes �
> DTD1 sont aussi conformes � DTD2.
> 
> Par exemple, DTD1 :
> <!ELEMENT Personne (Nom, Adresse)>
> <!ELEMENT Nom (#PCDATA)>
> <!ELEMENT Adresse (#PCDATA)>
> 
> et DTD2 :
> <!ELEMENT Personne ((Nom, Adresse)|(NumCli))>
> <!ELEMENT Nom (#PCDATA)>
> <!ELEMENT Adresse (#PCDATA)>
> <!ELEMENT NumCli (#PCDATA)>
> 
> il semble clair que tous les documents conformes � DTD1 le seront
> �galement � DTD2.
> 
> Ma question est la suivante :
> - Existe-t-il un terme d�signant une telle relation entre deux DTD's

Inclusion. Un modele de contenu (une expression reguliere) definit un
langage (un ensemble de mots sur l'alphabet comportant un symbole pour
chaque type d'element).

> - Si oui, existe-t-il des documents la d�crivant ?

N'importe quel livre d'info theorique, qui parle de langages formels
et/ou de theorie des langages. Je crois qu'il y a aussi une section
"Theory" a http://xml.cover-pages.org (je ne suis pas sur de l'url).

> - Existe-t-il des outils permettant de v�rifier que deux DTD v�rifient
> une telle relation?

C'est un probleme NP-complet il me semble (l'equivalence de deux e.r.
l'est, et si on avait un moyen polynomial de tester l'inclusion on en
aurait aussi un pour tester l'equivalence).

ET ca c'est seulement en testant element par element. On pourrait
imaginer vouloir ignorer des elements a contenu purement elementaire,
ou autre fantaisie.

Donc : "on n'est jamais assez fort pour ce calcul" (*)

Il me semble avoir lu le resume d'un article expliquant un algo
exponentiel (evidemment) mais utilisable dans la pratique (un peu
comme l'inference de type en ML). Si quelqu'un a une reference, elle
est bienvenue...

-- Alain.

(*) c'est une contrepeterie.