Exact XML type checking in polynomial time

Sebastian Maneth, Thomas Perst, Helmut Seidl

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

35 Scopus citations

Abstract

Stay macro tree transducers (smtts) are an expressive formalism for reasoning about XSLT-like document transformations. Here, we consider the exact type checking problem for smtts. While the problem is decidable, the involved technique of inverse type inference is known to have exponential worst-case complexity (already for top-down transformations without parameters). We present a new adaptive type checking algorithm based on forward type inference through exact characterizations of output languages. The new algorithm correctly type-checks all call-by-value smtts. Given that the output type is specified by a deterministic automaton, the algorithm is polynomial-time whenever the transducer uses only few parameters and visits every input node only constantly often. Our new approach can also be generalized from smtts to stay macro forest transducers which additionally support concatenation as built-in output operation.

Original languageEnglish
Title of host publicationDatabase Theory, ICDT 2007 - 11th International Conference, Proceedings
Pages254-268
Number of pages15
DOIs
StatePublished - 2006
Event11th International Conference on Database Theory, ICDT 2007 - Barcelona, Spain
Duration: 10 Jan 200712 Jan 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4353 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Conference on Database Theory, ICDT 2007
Country/TerritorySpain
CityBarcelona
Period10/01/0712/01/07

Fingerprint

Dive into the research topics of 'Exact XML type checking in polynomial time'. Together they form a unique fingerprint.

Cite this