Typechecking for XML transformers

By Tova Milo, Dan Suciu, Victor Vianu. Journal of computer and system sciences (Print), 2000

319 citations recorded by the source corpus.

We study the typechecking problem for XML 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 nobust 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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/8c9879ef6bfd14afe5b05b5e943034646e75ae99

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Finite state machines for strings over infinite alphabets (2004, methodology): “When the input is restricted to a .nite alphabet, PAs recognize the regular languages, even in the presence of alternation [Milo et al. 2000].”
Efficient algorithms for processing XPath queries (2002, background): “…data stream processing) [Altinel and Franklin 2000; Chan et al. 2002; Green et al. 2003; Peng and Chawathe 2003; Gupta and Suciu 2003; Bar-Yossef et al. 2004] and on related problems such as structural joins and XML query pattern matching [Bruno et al. 2002; Chan et al. 2002; Al-Khalifa et al.…”