%0 Journal Article %1 Milo200366 %A Milo, Tova %A Suciu, Dan %A Vianu, Victor %D 2003 %J Journal of Computer and System Sciences %K semantic set types xml %N 1 %P 66--97 %R DOI: 10.1016/S0022-0000(02)00030-2 %T Typechecking for XML transformers %U http://www.sciencedirect.com/science/article/B6WJ0-47XFTX0-2/2/1902bfd80697c4acada49ee5b45fd73b %V 66 %X We study the typechecking problem for XML (eXtensible Markup Language) transformers: given an XML transformation program and a DTD for the input XML documents, check whether every result of the program conforms to a specified output DTD. We model XML transformers using a novel device called a k-pebble transducer, that can express most queries without data-value joins in XML-QL, XSLT, and other XML query languages. Types are modeled by regular tree languages, a robust extension of DTDs. The main result of the paper is that typechecking for k-pebble transducers is decidable. Consequently, typechecking can be performed for a broad range of XML transformation languages, including XML-QL and a fragment of XSLT.

@article{Milo200366, abstract = {We study the typechecking problem for XML (eXtensible Markup Language) transformers: given an XML transformation program and a DTD for the input XML documents, check whether every result of the program conforms to a specified output DTD. We model XML transformers using a novel device called a k-pebble transducer, that can express most queries without data-value joins in XML-QL, XSLT, and other XML query languages. Types are modeled by regular tree languages, a robust extension of DTDs. The main result of the paper is that typechecking for k-pebble transducers is decidable. Consequently, typechecking can be performed for a broad range of XML transformation languages, including XML-QL and a fragment of XSLT.}, added-at = {2009-09-01T09:30:01.000+0200}, author = {Milo, Tova and Suciu, Dan and Vianu, Victor}, biburl = {https://www.bibsonomy.org/bibtex/282ce564b81630103f1c91912f78ee279/q}, description = {ScienceDirect - Journal of Computer and System Sciences : Typechecking for XML transformers*1}, doi = {DOI: 10.1016/S0022-0000(02)00030-2}, interhash = {41e09aafbfc769d695f00fee930375b2}, intrahash = {82ce564b81630103f1c91912f78ee279}, issn = {0022-0000}, journal = {Journal of Computer and System Sciences}, keywords = {semantic set types xml}, note = {Special Issue on PODS 2000}, number = 1, pages = {66--97}, timestamp = {2009-09-01T09:30:01.000+0200}, title = {Typechecking for XML transformers}, url = {http://www.sciencedirect.com/science/article/B6WJ0-47XFTX0-2/2/1902bfd80697c4acada49ee5b45fd73b}, volume = 66, year = 2003 }