Abstract
This paper discusses subtyping of tree-structured data encountered on the Web, e.g. XML and HTML data. Our long range objective is to de ne a type system for Web and/or Semantic Web query languages amenable to static type checking. We propose a type formalism motivated by XML Schema and accommodating two concepts of subtyping: inclusion subtyping (corresponding to XML Schema notion of type restriction) and extension subtyping (motivated by XML Schema's type extension). We present algorithms for checking both kinds of subtyping. The algorithms are polynomial if certain conditions are imposed on the type de nitions; the conditions seem natural and not too restrictive.

URL:
http://rewerse.net/publications/rewerse-publications.html#REWERSE-RP-2004-11

BibTeX:

@inproceedings{REWERSE-RP-2004-11,
	author = {Fran\c{c}ois Bry and W\lodzimierz Drabent and Jan Ma\luszyński},
	title = {On Subtyping of Tree-structured Data A Polynomial Approach},
	booktitle = {Proceedings of Workshop on Principles and Practice of Semantic Web Reasoning, St. Malo, France (6th--10th September 2004)},
	year = {2004},
	volume = {3208},
	organization = {REWERSE},
	series = {LNCS},
	url = {http://rewerse.net/publications/rewerse-publications.html#REWERSE-RP-2004-11}
}